Indexing with Grid Variable Distance : efficient nearest neighbor query processing, 2013

Item — Call Number: MU Thesis Ele

Identifier: b7667111

Scope and Contents

From the Collection:

The collection consists of theses written by students enrolled in the Monmouth University graduate Computer Science program. The holdings are primarily bound print documents that were submitted in partial fulfillment of requirements for the Master of Science degree.

Dates

Creation: 2013

Creator

Eleneski, Andrew (Author, Person)
Yu, Cui (Thesis advisor, Person)

Conditions Governing Access

All analog collection holdings are limited to library use only.

Collection holdings may not be borrowed through Interlibrary Loan.

Researchers seeking to photocopy collection materials must complete an Application to Photocopy Form.

Any photocopying of collection materials will be performed by the Monmouth University Library staff.

The Monmouth University Library reserves the right to limit or refuse duplication requests subject to the condition of collection materials and/or restrictions imposed by the collection creators or by the United States Copyright Act.

Permission to examine, or copy, collection materials does not imply permission to publish or quote. It is the responsibility of the researcher to obtain such permissions from both the copyright holder and Monmouth University.

Full Extent

1 Items (print book) : 82 pages ; 8.5 x 11.0 inches (28 cm).

Language of Materials

English

Additional Description

Abstract

Over the years, there have been many attempts at improving the performance of nearest neighbor queries. This is an important endeavor because of the wide variety of uses of nearest neighbor searches, from geographic information systems (GIS) to databases to recommendation systems. An example is when a car is running low on fuel while driving; the GPS may be able to report the three closest gas stations to a cars [sic] current location.

This thesis provides the introduction of the Grid Variable Distance (GVD) approach of performing nearest neighbor searches that extends upon ideas of the iDistance approach of breaking up a d-dimensional area into a one-dimensional indexing scheme. Where iDistance has user determined reference points, GVD has reference points defined by the configurable dimension and subdivision. The GVD approach attempts to improve performance and I/O cost against other methods to make k-nearest-neighbor (kNN) processing faster and more efficient. The new approach is tested against both iDistance and R-Tree with uniform, normalized and real datasets. The results of the experiments show that the GVD approach processes queries faster with less I/O cost then both iDistance and R-Tree up to 14 dimensions.

Partial Contents

Abstract -- Acknowledgements -- Table of contents -- List of tables -- List of figures -- 1. Introduction -- 2. Related work -- 3. Design and implementation -- 4. Testing and results -- 5. Conclusion -- Appendix -- Bibliography.