%0 Conference Paper %B IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008 %D 2008 %T Network-Aware Join Processing in Global-Scale Database Federations %A Xiaodan Wang %A Burns,R. %A Terzis,A. %A Deshpande, Amol %K Astronomy %K Computer networks %K Concurrent computing %K global-scale database federations %K join scheduling algorithms %K network utilization %K network-aware join processing %K parallel schedules %K polynomial-time algorithm %K Polynomials %K Processor scheduling %K Query processing %K reduce resource usage %K Scheduling algorithm %K Spatial databases %K spatial-join queries %K Telecommunication traffic %K Throughput %X We introduce join scheduling algorithms that employ a balanced network utilization metric to optimize the use of all network paths in a global-scale database federation. This metric allows algorithms to exploit excess capacity in the network, while avoiding narrow, long-haul paths. We give a two- approximate, polynomial-time algorithm for serial (left-deep) join schedules. We also present extensions to this algorithm that explore parallel schedules, reduce resource usage, and define tradeoffs between computation and network utilization. We evaluate these techniques within the SkyQuery federation of Astronomy databases using spatial-join queries submitted by SkyQuery's users. Experiments show that our algorithms realize near-optimal network utilization with minor computational overhead. %B IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008 %I IEEE %P 586 - 595 %8 2008/04/07/12 %@ 978-1-4244-1836-7 %G eng %R 10.1109/ICDE.2008.4497467 %0 Journal Article %J IEEE Internet Computing %D 2007 %T Client-Based Spatial Browsing on the World Wide Web %A Brabec,Frantisek %A Samet, Hanan %K client-server spatial browsing %K geographic information systems (GIS) %K Spatial databases %K web access %K web-based mapping %X Being able to visualize both spatial and nonspatial data is becoming increasingly important to today's Internet users. Spatial data viewers and query tools can aid in visualization, but they should also let users access data instantly and with minimal effort. The authors explore new ways to allow visualization of data stored in a central server database on a simple client. They also consider usage scenarios in which transferring the whole database to the client for processing isn't feasible due to the amount of data on the server, insufficient computing power on the client, and a slow link between the two. %B IEEE Internet Computing %V 11 %P 52 - 59 %8 2007/// %@ 1089-7801 %G eng %N 1 %0 Journal Article %J Information Processing Letters %D 2007 %T Execution time analysis of a top-down R-tree construction algorithm %A Alborzi,Houman %A Samet, Hanan %K Bulk loading %K Data structures %K Packing %K R-trees %K Spatial databases %X A detailed CPU execution-time analysis and implementation are given for a bulk loading algorithm to construct R-trees due to García et al. [Y.J. García, M.A. López, S.T. Leutenegger, A greedy algorithm for bulk loading R-trees, in: GIS'98: Proc. of the 6th ACM Intl. Symp. on Advances in Geographic Information Systems, Washington, DC, 1998, pp. 163–164] which is known as the top-down greedy split (TGS) bulk loading algorithm. The TGS algorithm makes use of a classical bottom-up packing approach. In addition, an alternative packing approach termed top-down packing is introduced which may lead to improved query performance, and it is shown how to incorporate it into the TGS algorithm. A discussion is also presented of the tradeoffs of using the bottom-up and top-down packing approaches. %B Information Processing Letters %V 101 %P 6 - 12 %8 2007/01/16/ %@ 0020-0190 %G eng %U http://www.sciencedirect.com/science/article/pii/S002001900600233X %N 1 %R 10.1016/j.ipl.2006.07.010 %0 Conference Paper %B Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems %D 2006 %T Distance join queries on spatial networks %A Sankaranarayanan,Jagan %A Alborzi,Houman %A Samet, Hanan %K location-based services %K path coherence %K Query processing %K SILC framework %K Spatial databases %K spatial networks %X The result of a distance join operation on two sets of objects R, S on a spatial network G is a set P of object pairs pq, p É R, q É S such that the distance of an object pair pq is the shortest distance from p to q in G. Several variations to the distance join operation such as UnOrdered, Incremental, topk, Semi-Join impose additional constraints on the distance between the object pairs in P, the ordering of object pairs in P, and on the cardinality of P. A distance join algorithm on spatial networks is proposed that works in conjunction with the SILC framework, which is a new approach to query processing on spatial networks. Experimental results demonstrate up to an order of magnitude speed up when compared with a prominent existing technique. %B Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems %S GIS '06 %I ACM %C New York, NY, USA %P 211 - 218 %8 2006/// %@ 1-59593-529-0 %G eng %U http://doi.acm.org/10.1145/1183471.1183506 %R 10.1145/1183471.1183506 %0 Conference Paper %B Visual Analytics Science And Technology, 2006 IEEE Symposium On %D 2006 %T A Visual Interface for Multivariate Temporal Data: Finding Patterns of Events across Multiple Histories %A Fails,J. A %A Karlson,A. %A Shahamat,L. %A Shneiderman, Ben %K ball-and-chain visualization %K Chromium %K Computer science %K Data analysis %K data visualisation %K Data visualization %K Database languages %K event pattern discovery %K Graphical user interfaces %K History %K Information Visualization %K Medical treatment %K multivariate temporal data %K Pattern analysis %K pattern recognition %K PatternFinder integrated interface %K Query processing %K query visualization %K result-set visualization %K Spatial databases %K tabular visualization %K temporal pattern discovery %K temporal pattern searching %K Temporal query %K user interface %K User interfaces %K visual databases %K visual interface %X Finding patterns of events over time is important in searching patient histories, Web logs, news stories, and criminal activities. This paper presents PatternFinder, an integrated interface for query and result-set visualization for search and discovery of temporal patterns within multivariate and categorical data sets. We define temporal patterns as sequences of events with inter-event time spans. PatternFinder allows users to specify the attributes of events and time spans to produce powerful pattern queries that are difficult to express with other formalisms. We characterize the range of queries PatternFinder supports as users vary the specificity at which events and time spans are defined. Pattern Finder's query capabilities together with coupled ball-and-chain and tabular visualizations enable users to effectively query, explore and analyze event patterns both within and across data entities (e.g. patient histories, terrorist groups, Web logs, etc.) %B Visual Analytics Science And Technology, 2006 IEEE Symposium On %I IEEE %P 167 - 174 %8 2006/11/31/Oct. %@ 1-4244-0591-2 %G eng %R 10.1109/VAST.2006.261421 %0 Conference Paper %B Proceedings of the 13th annual ACM international workshop on Geographic information systems %D 2005 %T Efficient query processing on spatial networks %A Sankaranarayanan,Jagan %A Alborzi,Houman %A Samet, Hanan %K location-based services %K path coherence %K Query processing %K SILC framework %K Spatial databases %K spatial networks %X A framework for determining the shortest path and the distance between every pair of vertices on a spatial network is presented. The framework, termed SILC, uses path coherence between the shortest path and the spatial positions of vertices on the spatial network, thereby, resulting in an encoding that is compact in representation and fast in path and distance retrievals. Using this framework, a wide variety of spatial queries such as incremental nearest neighbor searches and spatial distance joins can be shown to work on datasets of locations residing on a spatial network of sufficiently large size. The suggested framework is suitable for both main memory and disk-resident datasets. %B Proceedings of the 13th annual ACM international workshop on Geographic information systems %S GIS '05 %I ACM %C New York, NY, USA %P 200 - 209 %8 2005/// %@ 1-59593-146-5 %G eng %U http://doi.acm.org/10.1145/1097064.1097093 %R 10.1145/1097064.1097093 %0 Journal Article %J ACM Comput. Surv. %D 2004 %T Object-based and image-based object representations %A Samet, Hanan %K Access methods %K feature query %K geographic information systems (GIS) %K image space %K location query %K object space %K octrees %K Pyramids %K quadtrees %K R-trees %K space-filling curves %K Spatial databases %X An overview is presented of object-based and image-based representations of objects by their interiors. The representations are distinguished by the manner in which they can be used to answer two fundamental queries in database applications: (1) Feature query: given an object, determine its constituent cells (i.e., their locations in space). (2) Location query: given a cell (i.e., a location in space), determine the identity of the object (or objects) of which it is a member as well as the remaining constituent cells of the object (or objects). Regardless of the representation that is used, the generation of responses to the feature and location queries is facilitated by building an index (i.e., the result of a sort) either on the objects or on their locations in space, and implementing it using an access structure that correlates the objects with the locations. Assuming the presence of an access structure, implicit (i.e., image-based) representations are described that are good for finding the objects associated with a particular location or cell (i.e., the location query), while requiring that all cells be examined when determining the locations associated with a particular object (i.e., the feature query). In contrast, explicit (i.e., object-based) representations are good for the feature query, while requiring that all objects be examined when trying to respond to the location query. The goal is to be able to answer both types of queries with one representation and without possibly having to examine every cell. Representations are presented that achieve this goal by imposing containment hierarchies on either space (i.e., the cells in the space in which the objects are found), or objects. In the former case, space is aggregated into successively larger-sized chunks (i.e., blocks), while in the latter, objects are aggregated into successively larger groups (in terms of the number of objects that they contain). The former is applicable to image-based interior-based representations of which the space pyramid is an example. The latter is applicable to object-based interior-based representations of which the R-tree is an example. The actual mechanics of many of these representations are demonstrated in the VASCO JAVA applets found at http://www.cs.umd.edu/˜hjs/quadtree/index.html. %B ACM Comput. Surv. %V 36 %P 159 - 217 %8 2004/06// %@ 0360-0300 %G eng %U http://doi.acm.org/10.1145/1031120.1031123 %N 2 %R 10.1145/1031120.1031123 %0 Conference Paper %B Proceedings of the 11th ACM international symposium on Advances in geographic information systems %D 2003 %T The internet spatial spreadsheet: enabling remote visualization of dynamic spatial data and ongoing query results over a network %A Iwerks,Glenn S. %A Samet, Hanan %K client server %K GIS %K Spatial databases %K Visualization %X Moving object databases store and process data for objects that change location frequently. Materialized views maintained over time must be updated to reflect changes due to the motion of objects in their environment. To visualize view query results, displays must be updated to reflect the change. In this paper we present the Internet Spatial Spreadsheet (ISS) as a means to organize, query, and visualize changing spatial data in a network environment such as the Internet.The goal of the ISS is to keep client visualizations of query results up to date with the server state. This is accomplished by pushing the minimal set of spatial data needed for rendering query results on the client. Incremental changes to query results are subsequently transmitted to the client as the database is updated to keep the visualization current. Additional constraints in the network environment such as firewall limitations are also considered. %B Proceedings of the 11th ACM international symposium on Advances in geographic information systems %S GIS '03 %I ACM %C New York, NY, USA %P 154 - 160 %8 2003/// %@ 1-58113-730-3 %G eng %U http://doi.acm.org/10.1145/956676.956697 %R 10.1145/956676.956697 %0 Journal Article %J ACM Trans. Database Syst. %D 2003 %T Iterative spatial join %A Jacox,Edwin H. %A Samet, Hanan %K external memory algorithms %K plane-sweep %K Spatial databases %K Spatial join %X The key issue in performing spatial joins is finding the pairs of intersecting rectangles. For unindexed data sets, this is usually resolved by partitioning the data and then performing a plane sweep on the individual partitions. The resulting join can be viewed as a two-step process where the partition corresponds to a hash-based join while the plane-sweep corresponds to a sort-merge join. In this article, we look at extending the idea of the sort-merge join for one-dimensional data to multiple dimensions and introduce the Iterative Spatial Join. As with the sort-merge join, the Iterative Spatial Join is best suited to cases where the data is already sorted. However, as we show in the experiments, the Iterative Spatial Join performs well when internal memory is limited, compared to the partitioning methods. This suggests that the Iterative Spatial Join would be useful for very large data sets or in situations where internal memory is a shared resource and is therefore limited, such as with today's database engines which share internal memory amongst several queries. Furthermore, the performance of the Iterative Spatial Join is predictable and has no parameters which need to be tuned, unlike other algorithms. The Iterative Spatial Join is based on a plane sweep algorithm, which requires the entire data set to fit in internal memory. When internal memory overflows, the Iterative Spatial Join simply makes additional passes on the data, thereby exhibiting only a gradual performance degradation. To demonstrate the use and efficacy of the Iterative Spatial Join, we first examine and analyze current approaches to performing spatial joins, and then give a detailed analysis of the Iterative Spatial Join as well as present the results of extensive testing of the algorithm, including a comparison with partitioning-based spatial join methods. These tests show that the Iterative Spatial Join overcomes the performance limitations of the other algorithms for data sets of all sizes as well as differing amounts of internal memory. %B ACM Trans. Database Syst. %V 28 %P 230 - 256 %8 2003/09// %@ 0362-5915 %G eng %U http://doi.acm.org/10.1145/937598.937600 %N 3 %R 10.1145/937598.937600 %0 Conference Paper %B 16th International Conference on Pattern Recognition, 2002. Proceedings %D 2002 %T Virtual audio system customization using visual matching of ear parameters %A Zotkin,Dmitry N %A Duraiswami, Ramani %A Davis, Larry S. %A Mohan,A. %A Raykar,V. %K acoustic signal processing %K Audio systems %K Auditory system %K Computer vision %K database %K Ear %K ear parameter matching %K geometrical measurements %K Head %K head related transfer functions %K HRTF customization %K Image databases %K IMAGE PROCESSING %K medical image processing %K performance improvement %K Position measurement %K sonification %K Spatial databases %K System testing %K Transfer functions %K virtual audio system customization %K virtual auditory spaces %K virtual auditory system %K visual matching %X Applications in the creation of virtual auditory spaces (VAS) and sonification require individualized head related transfer functions (HRTFs) for perceptual fidelity. HRTFs exhibit significant variation from person to person due to differences between their pinnae, and their body sizes. We propose and preliminarily implement a simple HRTF customization based on the use of a published database of HRTFs (Algazi et al., 2001) that also contains geometrical measurements of subject pinnae. We measure some of these features via simple image processing, and select the HRTF that has features most closely corresponding to the individual's features. This selection procedure is implemented along with the virtual auditory system described in (Zotkin et al., 2002), and listener tests conducted comparing the customized HRTF and a fixed HRTF. Despite the simplicity of the method, tests reveal average improvement in localization accuracy of about 25 percent, though performance improvement varies with source location and individuals. %B 16th International Conference on Pattern Recognition, 2002. Proceedings %I IEEE %V 3 %P 1003- 1006 vol.3 - 1003- 1006 vol.3 %8 2002/// %@ 0-7695-1695-X %G eng %R 10.1109/ICPR.2002.1048207 %0 Conference Paper %B , First International Workshop on Interoperability in Multidatabase Systems, 1991. IMS '91. Proceedings %D 1991 %T An algebra and calculus for relational multidatabase systems %A Grant,J. %A Litwin,W. %A Roussopoulos, Nick %A Sellis,T. %K Algebra %K autonomous databases %K Calculus %K Computer networks %K Computer science %K Data models %K Data structures %K Database systems %K database theory %K distributed databases %K Military computing %K multidatabase manipulation language %K multidatabase system %K multirelational algebra %K query languages %K relational algebra %K Relational databases %K Spatial databases %K theoretical foundation %X With the existence of many autonomous databases widely accessible through computer networks, users will require the capability to jointly manipulate data in different databases. A multidatabase system provides such a capability through a multidatabase manipulation language. The authors propose a theoretical foundation for such languages by presenting a multirelational algebra and calculus based on the relational algebra and calculus. The proposal is illustrated by various queries on an example multidatabase %B , First International Workshop on Interoperability in Multidatabase Systems, 1991. IMS '91. Proceedings %I IEEE %P 118 - 124 %8 1991/04// %@ 0-8186-2205-9 %G eng %R 10.1109/IMS.1991.153694 %0 Journal Article %J IEEE Transactions on Software Engineering %D 1988 %T An efficient pictorial database system for PSQL %A Roussopoulos, Nick %A Faloutsos,C. %A Sellis,T. %K alphanumeric encodings %K Computer science %K Data structures %K Database languages %K database management systems %K Database systems %K Encoding %K Image coding %K Image databases %K multidimensional B-trees %K Object oriented databases %K pictorial database system %K PSQL %K query language %K query languages %K R+-trees %K Relational databases %K Spatial databases %K spatial objects %K spatial search %K User interfaces %X Pictorial databases require efficient and direct spatial search based on the analog form of spatial objects and relationships instead of search based on some cumbersome alphanumeric encodings of the pictures. A description is given of PSQL, a query language that allows pictorial domains to be presented to the user in their analog form and allows him or her to do direct manipulation on the objects found on those domains. Direct spatial search and computation on the pictures is done using efficient data structures, R- and R+-trees (multidimensional B-trees), which are excellent devices for searching spatial objects and relationships found on pictures %B IEEE Transactions on Software Engineering %V 14 %P 639 - 650 %8 1988/05// %@ 0098-5589 %G eng %N 5 %R 10.1109/32.6141