Scholars' Mine
Missouri S&T
Research Repository
Curtis Laws Wilson Library
400 W. 14th Street
Rolla, MO 65409-0060
scholarsmine@mst.edu
| Title: | A scalable constraint-based q-hash indexing for moving objects |
| Author (s): | Francis, Deja Hepziba Madria, Sanjay Sabharwal, Chaman L. |
| Department/Lab Affiliations: | Computer Science |
| Keywords: | Moving object Quad-tree Query R-Tree |
| Subject Terms: | Indexing. |
| Issue Date: | 2008-03 |
| Publisher: | Elsevier |
| Citation: | Francis, Deja Hepziba., Madria, Sanjay., and Sabharwal, Chaman L. "A Scalable Constraint-Based Q-Hash Indexing for Moving Objects." Information Sciences, vol. 178, no. 6, (2008). |
| Abstract: | In this paper, we develop a Q-hash index structure to efficiently store the position of moving objects. An environment of moving objects contains continuously changing locations which are hard to index using traditional index structures such as R-trees, QuadTrees and their variants. In order to answer the queries accurately, one of the problems faced in storing these positions is the number of updates that have to be made to the database whenever locations change. The high maintenance overhead on updates leads to performance degradation of these index structures; additionally, it makes the database very bulky which results in very poor performance in terms of query execution time. One of the main objectives of the structure we propose is to minimize the number of updates to the database to an optimal number so that the accuracy and response time of the query result are not compromised and at the same time the number of wireless communications can be reduced. The indexing is done using a hashing technique where the hashing function makes use of a region based QuadTree structure. To improve the efficiency of the query processing our index structure helps us define constraints over speed, direction and location of the moving object at the device level which controls the number of updates. In addition, in order to answer different query types efficiently at all levels we propose a three-tier (moving object, regional server, central repository) architecture. Our extensive performance evaluation and comparison of the proposed technique concludes that our scheme outperforms existing Q + R-tree and QuadTree in terms of range query execution time by a high order of magnitude. |
| Type: | Article - Journal text |
| In Title: | Information Sciences |
| Copyright Notice: | This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder. FULL COPYRIGHT INFORMATION: |
| Publisher URL: | |
| Link to this page: |
| title | A scalable constraint-based q-hash indexing for moving objects |
| contributor.author | Francis, Deja Hepziba |
| contributor.author | Madria, Sanjay |
| contributor.author | Sabharwal, Chaman L. |
| contributor.deptlab | Computer Science |
| subject | Moving object |
| subject | Quad-tree |
| subject | Query |
| subject | R-Tree |
| subject.LCSH | Indexing. |
| date.issued | 2008-03 |
| publisher | Elsevier |
| identifier.citation | Francis, Deja Hepziba., Madria, Sanjay., and Sabharwal, Chaman L. "A Scalable Constraint-Based Q-Hash Indexing for Moving Objects." Information Sciences, vol. 178, no. 6, (2008). |
| identifier.pub.URI | |
| description.abstract | In this paper, we develop a Q-hash index structure to efficiently store the position of moving objects. An environment of moving objects contains continuously changing locations which are hard to index using traditional index structures such as R-trees, QuadTrees and their variants. In order to answer the queries accurately, one of the problems faced in storing these positions is the number of updates that have to be made to the database whenever locations change. The high maintenance overhead on updates leads to performance degradation of these index structures; additionally, it makes the database very bulky which results in very poor performance in terms of query execution time. One of the main objectives of the structure we propose is to minimize the number of updates to the database to an optimal number so that the accuracy and response time of the query result are not compromised and at the same time the number of wireless communications can be reduced. The indexing is done using a hashing technique where the hashing function makes use of a region based QuadTree structure. To improve the efficiency of the query processing our index structure helps us define constraints over speed, direction and location of the moving object at the device level which controls the number of updates. In addition, in order to answer different query types efficiently at all levels we propose a three-tier (moving object, regional server, central repository) architecture. Our extensive performance evaluation and comparison of the proposed technique concludes that our scheme outperforms existing Q + R-tree and QuadTree in terms of range query execution time by a high order of magnitude. |
| type | Article - Journal |
| type.DCMIType | text |
| type.status | Final version |
| relation.isPartOf | Information Sciences |
| rights | This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder. |
| rights.URI | |
| date.accessioned | 2007-04-11T17:00:48Z |
| date.available | 2008-04-11T19:49:08Z |
| identifier.persist.URI |