Processing generalized k-nearest neighbor queries on a wireless broadcast stream

Harim Jung, Yon Dohn Chung, Ling Liu

    Research output: Contribution to journalArticlepeer-review

    23 Citations (Scopus)

    Abstract

    In this paper, we investigate the problem of processing generalized k-nearest neighbor (GkNN) queries, which involve both spatial and non-spatial specifications for data objects, in a wireless broadcasting system. We present a method for processing GkNN queries on the broadcast stream. In particular, we propose a novel R-tree variant index structure, called the bit-vector R-tree (bR-tree), which stores additional bit-vector information to describe non-spatial attribute values of the data objects. In addition, each node in the bR-tree stores only one pointer to its children, which makes the bR-tree compact. We generate the broadcast stream by multiplexing the bR-tree and the data objects in the broadcasting channel. The corresponding search algorithm for the broadcast stream is also described. Through a series of comprehensive simulation experiments, we prove the efficiency of the proposed method with regard to energy consumption, latency, and memory requirement, which are the major performance concerns in a wireless broadcasting system. Furthermore, we test the practicality of the proposed method in a real prototype system.

    Original languageEnglish
    Pages (from-to)64-79
    Number of pages16
    JournalInformation Sciences
    Volume188
    DOIs
    Publication statusPublished - 2012 Apr 1

    Bibliographical note

    Funding Information:
    This work was supported by a Grant from the Korea Research Foundation , funded by the Korean Government ( KRF-2008-313-D00856 ).

    Keywords

    • Generalized k-nearest neighbor (GkNN) queries
    • Location-based services
    • Mobile databases
    • Wireless broadcasting systems

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Software
    • Control and Systems Engineering
    • Computer Science Applications
    • Information Systems and Management
    • Artificial Intelligence

    Fingerprint

    Dive into the research topics of 'Processing generalized k-nearest neighbor queries on a wireless broadcast stream'. Together they form a unique fingerprint.

    Cite this