Location-Dependent Database Access1. Introduction11. Terminology1.2. Location Dependent Data vs Spatial Data vs Temporal Data2. Architecture2.1. Global Positioning System – GPS2.2. LDS Middleware Architecture3. Overview of Location-Dependent QueriesFigure 4. LDQ vs. LAQ3.1. LDQ vs. Point location queries3.2. Classification of queries4. Overview of Moving Object Queries and Databases5. Location Modeling and Translation6. Nearest-neighbor Queries Through Point Location and Indexing6.1.Voronoi diagramFigure 6. The Voronoi diagram of a set of points.(pi) = {pIR2 | dist(p, pi) < dist(p, pj) for all j≠i}Figure 7. (a) A Voronoi cell of pi (filled region). (b) A Voronoi diagram in a bounded box.6.2. Related work in indexing techniques6.2.1. Kirkpatrick’s technique – triangulation6.2.2. Trapezoidal map6.2.3. K-d trees6.2.4. D-tree6.3. The N-tree: a new index structure for LDQ6.4. Summary of indexing techniques7. ConclusionsIn this paper we have provided a brief overview of location dependent data access, including LDQs, MODs, NN queries, and point queries. We have also examined indexing techniques to be used for them. A major emphasis of this paper was on nearest-neighbor queries.ReferencesLocation-Dependent Database AccessFaïza Najjar Sean Kelley, Margaret H. DunhamNational School of Computer Science Department of Computer Science and EngineeringLa Manouba 2010 PO Box 750122Tunisia Dallas, Texas [email protected] (kelley)[email protected]. Database queries stated in a mobile computing environment are significantly impacted by thatmobility. In this paper we provide an introduction into the subject of location dependent database access.The coverage is quite broad and is aimed as providing the reader with sufficient content and references tobegin research in this area. We include discussions of architecture and an overview of different types oflocation based mobile queries. A major portion of the paper deals with a detailed examination ofnearest-neighbor queries and Voronoi diagrams.Table of contents1. Introduction....................................................................................................................................12. Architecture................................................................................................................................83. Overview of Location-Dependent Queries.............................................................................114. Overview of Moving Object Queries and Databases............................................................135. Location Modeling and Translation.......................................................................................176. Nearest-neighborQueries Through Point Location and Indexing.......................................187. Conclusions...............................................................................................................................27References.....................................................................................................................................28Najjar, Kelley, Dunham11. IntroductionIn a mobile and wireless environment, efficient and consistent data access is a challenging research area,because of the weak connectivity and resource constraints. The mobile data access strategies can beessentially distinguished by delivery modes. The modes for server delivery can be described as clientpull, server-push, or hybrid:- Client pull (sometimes called on-demand access mode): A mobile client first submits a query viathe uplink channel and then “pulls” data, from the server through a wireless network (thedownlink channel), in the same manner as in a traditional client-server system. - The server-push (also called broadcast [15]): The mobile client receives information as a result ofhis or her whereabouts without having to actively submitting a query. The information sent to themobile client may be either on a public wireless channel (e.g. a welcome message when enteringa new town) or may be a subscription-based (e.g. alert system).- The hybrid delivery integrates both server-push and client pull delivery.Location-dependent data access assumes that a mobile user queries data where the value is dependent onhis/her location. A typical query of this type is:“Where is the closest restaurant?”This query may be stated explicity (in the client pull environment) or implicitly (in the pushenvironment). In a broadcast setting, a content provider can broadcast restaurant information for a localarea near the broadcast station. A Location Dependent Query (LDQ) is a mobile query where the result ofthe query depends on the location of the user making the query [4, 23, 26]. This definition can beexpanded to include a broadcast environment. Here the content of the broadcast is based on the locationof the broadcast station. Thus, as a mobile user roams, the result of his implicit query (that is the data thathe receives) changes. We conclude this section by reviewing some terms and background commonly used within location-dependent data and queries in wireless environments. We then briefly overview temporal and spatialdatabase concepts as these are important to understanding location dependent database access.Subsequent sections of this chapter examine architectural issues related to location dependent data access,an overview of location dependent queries, an overview of moving object databases and queries, locationmodeling and translation, and nearest neighbor queries and indexing.Najjar, Kelley, Dunham211. TerminologyAs long as people move across the earth’s surface, the need to know their current location anywhere andanytime has become a very important constraint in mobile databases. The term location refers to theposition of a point relative to a geometric subdivision or a given set of disjoint geometric objects [1, 16]. Before studying queries and data access approaches in mobile databases, it is important to emphasizesome fundamental properties of location data, such as:- Location models : we distinguish two kinds of location, geometric (or geographic) and. semantic(or symbolic) locations (see Figure 1): o The available mechanisms for identifying the geometric location can be divided into twobasic classes :1. A location is specified, in the World Geodic System 1984 (WGS84), as