International Business Machines Corporation

Roger Moussalli

Sameh W Asaad

Mudhakar Srivatsa

Dajung Lee

Bharat Sukhwani

A method of performing an evaluation of a spatial predicates for first and second regions includes receiving a first set of geohashes representing the first region, and receiving a second set of geohashes representing the second region. The method also includes for each geohash within the first set of geohashes: performing a respective pairwise evaluation of a first spatial primitive for the geohash within the first set and each of the geohashes within the second set to produce a set of first binary results corresponding to respective ones of the geohashes within the second set; and combining the set of first binary results using a first Boolean logic operator to produce one of a set of second binary results corresponding to respective ones of the geohashes within the first set. The method further includes combining the set of second binary results using a second Boolean logic operator to produce a third binary result corresponding to the first set of spatial primitives.

Spatial predicates evaluation on geohash-encoded geographical regions

A method of evaluating each of plurality of spatial primitives for a pair of geohashes is disclosed. The method comprises the steps of: detecting which of the pair of geohashes is a shorter geohash and which of the pair of geohashes is a longer geohash; identifying a breakpoint for the pair of geohashes; determining a set of one or more masks each associated with at least one of the pair of geohashes; evaluating a first one of the spatial primitives for the pair of geohashes, the first one of the spatial primitives being a 'contain' spatial primitive; and evaluating at least a second one of the spatial primitives for the pair of geohashes, the at least second one of the spatial primitives being at least one 'touch' spatial primitive.

An apparatus for converting between a geohash code and latitude/longitude coordinates includes a conversion module operative in one of at least first and second modes. In the first mode, the conversion module receives a geohash code, a number of geohash code bits remaining to be processed and an initial input interval, and generates first and second output intervals that are updated after each geohash code bit processed. The latitude and longitude coordinates are generated based on the first and second output intervals, respectively. In the second mode, the conversion module receives a latitude or longitude value, the number of geohash code bits remaining to be processed and the initial input interval, and generates a given one of the first and second output intervals. The conversion module is configured to process data at a rate of one geohash code bit per hardware cycle.

Enhanced conversion between geohash codes and corresponding longitude/latitude coordinates

A method for dynamically reconfiguring logic circuits on an FPGA includes the steps of: classifying a general function into sets of static functions and modal functions to be implemented on the FPGA; for each of the modal functions, generating a list of one-active actions; devising a circuit topology including at least a subset of look-up tables (LUTs) such that any one of the modal functions can be implemented at a time on the devised circuit topology; for each modal function, associating the devised circuit topology with a controller adapted to load a LUT configuration corresponding to a prescribed one of the one-active actions; implementing a single fixed circuit on the FPGA including devised circuit topologies for each of the modal functions; and updating contents of LUTs corresponding to the LUT configuration in the devised circuit topology when a change in modal function to be implemented on the FPGA is required.

Dynamically reconfigurable logic circuits using native field-programmable gate array primitives

Generating a data feed specific parser circuit is provided. An input of a number of bytes of feed data associated with a particular data feed that the data feed specific parser circuit is to process is received. A feed format specification file that describes a data format of the particular data feed is parsed to generate an internal data structure of the feed format specification file. A minimum number of parallel pipeline stages in the data feed specific parser circuit to process the number of bytes of feed data associated with the particular data is determined based on the generated internal data structure of the feed format specification file. Then, a description of the data feed specific parser circuit with the determined number of parallel pipeline stages is generated.

Growing community of inventors

Peekskill, NY, United States of America

Roger Moussalli