×

Progressive continuous range query for moving objects with a tree-like index

  • US 10,095,724 B1
  • Filed: 08/09/2017
  • Issued: 10/09/2018
  • Est. Priority Date: 08/09/2017
  • Status: Active Grant
First Claim
Patent Images

1. A progressive continuous range query (PCRQ) method, the method being performed by a system comprising a processor and a computer-readable medium having instructions stored thereon that perform the method when executed by the processor, the method comprising:

  • using branch-and-bound to index interest points with a tree-index;

    generating a nearest enter split point for a root node in the tree-index and adding to min-heap;

    generating a next nearest enter split point for the root node, a domain region of a node being a region that is generated by expanding a boundary of the root node by a specified range;

    inserting the generated split point into min-heap;

    when the obtained node is an internal node, collapsing the internal node by removing the internal node'"'"'s children from a temporary buffer of nodes, and adding the internal node to the temporary buffer; and

    when the obtained node is a leaf node, removing the leaf node from the list of points of interest, and reporting the list as a result;

    determining whether min-heap has more elements and whether a next split point in min-heap is closer than a destination;

    receiving a geographical location of a moving object;

    generating a query point representing the geographical location of the moving object;

    determining whether the query point has reached a split point;

    retrieving an entry that has generated the split point;

    removing the split point from min-heap;

    determining whether the split point is an enter split point; and

    determining again whether min-heap has more elements and whether a next split point in min-heap is closer than the destination.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×