Abstract:
A feature selection apparatus, including a computer readable storage medium storing a program, and a processor executing the program and configured to perform storing a spatio-temporal database in the computer readable storage medium, extracting data under a predetermined condition from the spatio-temporal database for sorting, receiving a query, and outputting the data according to the query of the spatio-temporal database.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
       [0001]    The present application is a Continuation application of U.S. patent application Ser. No. 14/291,714, filed on May 30, 2014, which is based on Japanese Patent Application No. 2013-118759 filed on Jun. 5, 2013, the entire contents of which are hereby incorporated by reference. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The present invention relates to a technique for querying a spatio-temporal database by stream processing. 
         [0004]    2. Description of Related Art 
         [0005]    Querying a spatio-temporal database by stream processing has recently been increasing as stream processing has become widespread. An example thereof is a ratings compilation system shown in  FIG. 1 . 
         [0006]    In  FIG. 1 , viewing information input from set top boxes (STBs) disposed in TVs in a plurality of homes from moment to moment includes a tuple {user ID (UserID), CH (channel), Time (current time)}. 
         [0007]    An input viewing information stream is compiled into a tuple {CH, Time (current time), num (rating)} by a stream processing operator referred to as a by-channel ratings compilation  102 . A stream processing operator referred to as an additional information acquisition  104  receives the tuple {CH, Time (current time), num (rating)}, queries a program database  106 , shown as a program table, stored in a hard disk drive of the computer system using channel (CH) in the tuple as a key, joins the result of the query and the tuple {CH, Time (current time), num (rating)} together to generate a tuple {CH, Time (current time), num (rating), Title (program name), . . . }, and outputs the tuple. The program database  106  is also referred to as a spatio-temporal database because it includes a time field. 
         [0008]    However, querying a spatio-temporal database from a stream processing operator in such a system needs a complicated description, such as schema mapping and SQL. An example of the description of SQL is as follows: 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 SELECT Title, ... FROM Program 
               
               
                   
                 WHERE CH = ? and Start &lt;= CT and End &gt; CT 
               
               
                   
                 //, where CT is the time stamp of a current time. 
               
               
                   
                   
               
             
          
         
       
     
         [0009]    Furthermore, if real-time stream processing is required, further optimization is needed. Specifically, a database querying process that involves accessing a hard disk drive causes a bottleneck in access. However, loading data in a database into a main memory has difficulty because it consumes too much memory. Furthermore, using a cache of the database is also difficult because query parameters include a current time. 
         [0010]    For such processes, the following conventional technique is known. First, Japanese Unexamined Patent Application Publication No. 2006-338432 discloses a stream-data processing system that provides a mechanism for replicating part or all of stream data and archiving the replication into a non-volatile storage means medium to allow the real-time data and the archive data to be used seamlessly and a mechanism for connecting a plurality of stream-data processing systems to enhance the performance of a query process. 
         [0011]    Japanese Unexamined Patent Application Publication No. 2007-328716 discloses a method for reducing the number of accesses to a database to enhance the performance by providing a stream predict cache, which is a hierarchical cache of relation data that can be predicted as a target to be compared with stream data. 
         [0012]    Japanese Unexamined Patent Application Publication No. 2011-28658 discloses a database unit that tracks the latest cache entry in a cache with a cache tracker of a cache device, records the cache entry on a cache management table, and if a base-table updating process occurs, identifies data that is influenced by the base-table updating process, on the base table present in the cache, transmits a message to abandon the cache entry of the identified data to the cache device, in which the cache device discards the cache entry in the cache designated by the discard message. 
         [0013]    Mohamed F. Mokbel, Xiaopeng Xiong, Walid G. Aref, Susanne E. Hambrusch, Sunil Prabhakar, and Moustafa A. Hammad, “PLACE: a query processor for handling real-time spatio-temporal data streams”, VLDB &#39;04 Proceedings of the Thirtieth international conference on Very large data bases—Volume 30 Pages 1377-1380 describes a technique for implementing spatio-temporal data for searching for an object included in a certain area. 
         [0014]    T. Y. Cliff Leung, and Richard R. Muntz, “Generalized data stream indexing and temporal query processing”, Research Issues on Data Engineering, 1992: Transaction and Query Processing, Second International Workshop on 2-3 Feb. 1992, Pages 124-131 describes a proposal for building an index for implementing various kinds of joining of spatio-temporal data. 
         [0015]    However, these conventional techniques do not suggest solving the problem of performance in querying a spatio-temporal database from a stream processing operator. 
       BRIEF SUMMARY OF THE INVENTION 
       [0016]    One aspect of the present invention provides a system for querying a database including: a storage means; a processor communicatively coupled to the storage means; and a feature selection module communicatively coupled to the storage means and the processor, wherein the feature selection module is configured to perform the steps of a method including: storing a database in the storage means, the database including a time field; extracting data in a predetermined period from a current time from the database; sorting the data by the time field; buffering the sorted data in a main memory; receiving a query including time; and outputting the data buffered on the basis of the time field as a stream. 
         [0017]    Another aspect of the present invention provides a computer implemented method for querying a database, the method including the steps of: extracting data in a predetermined period from a current time from a database including a time field stored in a storage means; sorting the data by the time field; buffering the data in a main memory; receiving a stream including time; outputting the data that is buffered on the basis of the time field as a stream; of the buffered data, joining data matching a predetermined matching condition; and outputting the matched data. 
         [0018]    Yet another aspect of the present invention provides a computer program product for querying a database, the program causing the computer to execute the steps of: extracting data in a predetermined period from a current time from a database stored in a storage means, the database including a time field; sorting the data by the time field; buffering the sorted data in a main memory; receiving a stream including time; outputting the data that is buffered on the basis of the time field as a stream; of the buffered data, joining data matching a predetermined matching condition; and outputting the matched data. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0019]      FIG. 1  is a diagram showing, in outline, a conventional ratings compilation system. 
           [0020]      FIG. 2  is a diagram showing a hardware configuration for implementing an embodiment of the present invention. 
           [0021]      FIG. 3  is a functional block diagram of an embodiment of the present invention. 
           [0022]      FIG. 4  is a flowchart of the process of a buffer-table generation routine. 
           [0023]      FIG. 5  is a diagram showing a state in which data is extracted from a program table to a buffer table. 
           [0024]      FIG. 6  is a flowchart of the process of a data-stream generation routine. 
           [0025]      FIG. 7  is a flowchart of a temporal joining process. 
           [0026]      FIG. 8  is a flowchart of a temporal joining process. 
           [0027]      FIG. 9  is a diagram of an example of related art in which a joining process is performed on a plurality of databases. 
           [0028]      FIG. 10  is a diagram of an example of a configuration of an embodiment of the present invention in which a joining process is performed on a plurality of databases. 
           [0029]      FIG. 11  is a diagram of an example of a road congestion pricing system. 
           [0030]      FIG. 12  is a diagram showing an example of a stock ordering process under temporal restriction. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0031]    Accordingly, an object of the present invention is to provide a technique for implementing stream processing capable of using data in a spatio-temporal database. 
         [0032]    The present invention solves the above problem by generating a data stream based on time data in the records of a spatio-temporal database and implementing a data stream operation considering space and time. 
         [0033]    Here, terms used in the description of the present invention are defined as follows: a spatio-temporal data stream includes the term of validity (start time and end time) in a tuple in a stream. Such a tuple is also referred to as a spatio-temporal tuple. A spatio-temporal data stream process is a stream process that selectively performs processing depending on the term of validity of the tuple. Temporal joining is joining tuples in which terms of validity overlap. 
         [0034]    A process according to an embodiment of the present invention includes the process of generating a spatio-temporal data stream from a spatio-temporal database and a spatio-temporal data stream process that performs temporal joining. 
         [0035]    A system according to an aspect of the present invention executes the following steps in the process of generating a spatio-temporal data stream from a spatio-temporal database: Sorting records in the spatio-temporal database in order of validity start time in the records and regularly buffering records in a fixed time from a current time into a main memory or the like. And outputting a record in the buffer as a spatio-temporal tuple at the point where the validity start time of the record is reached. 
         [0036]    Preferably, in the process of generating the spatio-temporal data stream from the spatio-temporal database, the system according to the aspect of the present invention executes the process of transmitting a notification about the expiration of the validity of a record in the buffer to a spatio-temporal stream receiving side at the point where the validity end time of the record is reached. 
         [0037]    The system according to the aspect of the present invention further executes the following steps in the spatio-temporal data stream process: Selecting a target spatio-temporal tuple using the term of validity of an input spatio-temporal tuple and performing a stream process. As a result, the output is also a spatio-temporal tuple. And deleting a spatio-temporal tuple buffered in an operator at the point where the term of validity expires. 
         [0038]    Preferably, in the spatio-temporal data stream process, the system according to an embodiment of the present invention further executes the step of flashing the spatio-temporal tuple buffered in the operator at the time when receiving the validity end time. 
         [0039]    According to an embodiment of the present invention, the process of joining records in a spatio-temporal database with input stream data can be performed at high speed by sorting the records in order of validity start time, regularly buffering records in a fixed time from a current time into a main memory or the like, and generating stream data on the basis thereof. 
         [0040]    The present invention generates a data stream based on time data in the records of a spatio-temporal database and implements a data stream operation considering space and time. In the process of generating a spatio-temporal data stream from a spatio-temporal database, records in the spatio-temporal database are sorted in order of validity start time in the records, records in a fixed time from a current time are regularly buffered into a main memory or the like, and the records in the buffer are output as a spatio-temporal tuple at the point where the validity start time of the records is reached. In the spatio-temporal data stream generating process, the process of selecting a target spatio-temporal tuple and a stream process are performed using the term of validity of an input spatio-temporal tuple. The process of deleting a spatio-temporal tuple buffered in an operator is executed at the point where the time of validity expires. 
         [0041]    Embodiments of the present invention will be described below with reference to the drawings. It should be understood that these embodiments are merely for explaining preferred forms of the present invention and are not intended to limit the scope of the present invention. The same reference sign denote the same object in all of the drawings unless otherwise noted. 
         [0042]      FIG. 2  is a diagram showing, in outline, an example of the configuration of a system for implementing the present invention. The present invention will be described using a viewing-information compilation system as an example, although not limited thereto. 
         [0043]    In  FIG. 2 , set top boxes (STBs)  204   a  to  204   z  disposed in TVs at individual homes are connected to the Internet  202  and transmit information about the users ID, channels (CH), and times of the STBs  204   a  to  204   z  via the Internet  202 . 
         [0044]    The tuples, each including the information about the user ID, channel (CH), and time, are transmitted from the STBs  204   a  to  204   z  to the Internet  202  are received by a server  206   a.    
         [0045]    The server  206   a  is connected to a network  208 , which is LAN, WAN, FHHT, or another connecting configuration. The network  208  is also connected to servers  206   b  to  206   n ,  210 , and  214 . Examples of the servers  206   b  to  206   n ,  210 , and  214  include IBM® System X, System i, and System p available from International Business Machines Corporation, although not limited thereto. Examples of operating systems usable in these servers include AIX™, UNIX™, Linux™, Windows™ 2008 servers. These embodiments use Linux™ servers. 
         [0046]    The servers  206   a  to  206   n  install IBM® InfoSphere Streams, and thus the servers  206   a  to  206   n  serve as stream servers. The number of stream servers can be either one or more, which depends on the throughput of stream data. 
         [0047]    The server  210  is a database server, to which a database  212  is connected. The database  212  can either be stored in a local disk drive of the server  210  or be connected to the database server  210  via a network, such as a storage means area network (SAN) or a network attached storage means (NAS). The server  210  installs a database management program, such as DB2. The database  212  includes a program database. The program database includes channel (CH), start time (START), end time (END), and title (TITLE) fields. 
         [0048]    The server  214  is an application server, which installs a Linux™ operating system and an IBM® WebSphere™ application server (WAS) in Java®. The server  214  connects to a client computer  216 . The administrator or operator operates the client computer  216  to appropriately change the configurations of the servers  206   a  to  206   n , which are stream servers, and the server  210 , which is a database server, through a WAS management tool or the like. 
         [0049]    Referring next to  FIG. 3 , the functional configuration of the process of an embodiment of the present invention will be described. In  FIG. 3 , a program table  302  is included in the database  212  in  FIG. 2  and includes channel (CH), start time (START), end time (END), title (TITLE) fields. 
         [0050]    A buffer-table generation routine  304  is preferably stored in a hard disk drive (not shown) of the server  210  and has the function of extracting records from the program table  302  under a predetermined condition to generate a buffer table  306  by operation. The buffer table  306  preferably sorts data in a fixed time (for example, 30 minutes) after a current time in order of START and loads the data into a main storage means (not shown) of one of the stream servers  206   a  to  206   n . The buffer-table generation routine  304  can be created in an appropriate existing computer programming language, such as Java®, C, C++, or C#. The process of the buffer-table generation routine  304  will be described later with reference to a flowchart in  FIG. 4 . 
         [0051]    A by-channel ratings compilation operator  308  is created in, for example, a streams processing language (SPL) used in IBM® InfoSphere Streams, so as to run in a stream server. The by-channel ratings compilation operator  308  compiles tuples [UserID, CH (channel), Time (current time)] received from the STBs  204   a  to  204   z  at intervals of a fixed time and outputs a tuple [CH (channel), Time (current time), num (rating)]. 
         [0052]    A data-stream generation routine  310  outputs a spatio-temporal tuple [CH, START, END, TITLE, . . . ] at the point where the current time reaches START. The data-stream generation routine  310  can also be created in an appropriate stream language, such as the SPL. An example of a code therefor is as follows: 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 stream&lt;Temporal_tuple&gt; T_stream = GenTemporal( ) { 
               
               
                   
                 param 
               
               
                   
                 table: Program 
               
               
                   
                 timeS: Program.Start 
               
               
                   
                 timeE: Program.End 
               
               
                   
                 } 
               
               
                   
                   
               
             
          
         
       
     
         [0053]    The process of the data-stream generation routine  310  will be described later with reference to a flowchart in  FIG. 6 . 
         [0054]    Preferably, a temporal joining operator  312  is also written in the SPL used in IBM InfoSphere Streams so as to run in a stream server. The temporal joining operator  312  receives a stream output from the by-channel ratings compilation operator  308  and a stream output from the data-stream generation routine  310 , joins the streams in terms of time, and outputs a stream [CH, Time (current time), num (rating), Title (program name), . . . ]. 
         [0055]    An example of a code therefor is as follows: 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 stream&lt;Combined_tuple&gt; Join = 
               
               
                   
                 TemporalJoin(Input_stream: T_stream) { 
               
               
                   
                 param 
               
               
                   
                 match: Input_stream.CH = T_stream.CH 
               
               
                   
                 } 
               
               
                   
                   
               
             
          
         
       
     
         [0056]    The process of the temporal joining operator  312  will be described later with reference to flowcharts in  FIGS. 7 and 8 . 
         [0057]    Referring next to the flowchart in  FIG. 4 , the process of the buffer-table generation routine  304  will be described. 
         [0058]    In  FIG. 4 , the buffer-table generation routine  304  sets Time0=current in step  402 , and steps  404  to  416  are a loop executed at intervals of time n, where n is a value smaller than x, described below. 
         [0059]    In step  406 , the buffer-table generation routine  304  sets Querytime=Time0+x. This means that data in which start time is after time x is to be obtained. 
         [0060]    The buffer-table generation routine  304  queries a database, that is, the program table  302 , in step  408 , under the condition of Time0&lt;=[START] and [START] &lt;Querytime. Here, START indicates a start time field in the program table  302 . 
         [0061]    The buffer-table generation routine  304  sorts the obtained data in chronological order in START time in step  410  and stores the sorted data in the buffer table  306  in step  412 . In step  414 , the buffer-table generation routine  304  sets Time0=Querytime and returns to step  404 , in which it enters the next loop after waiting for time n. 
         [0062]      FIG. 5  shows a state in which data is stored from the program table  302  into the buffer table  306  by the buffer-table generation routine  304 .  FIG. 5  shows that data in which start time is after 12:00 is stored in the buffer table  306 . 
         [0063]    Referring next to the flowchart in  FIG. 6 , the process of the data-stream generation routine  310  will be described. 
         [0064]    In step  602  of  FIG. 6 , the data-stream generation routine  310  points the first record on the buffer table  306 . 
         [0065]    The process from steps  604  to  620  is an external loop. In step  606 , the data-stream generation routine  310  sets the current time to Currenttime. 
         [0066]    The process from steps  608  to  618  is an inner loop. In step  610 , the data-stream generation routine  310  determines whether the start time of the pointed record has reached Currenttime, and if not, the process returns to step  604 . 
         [0067]    If the start time of the pointed record has reached Currenttime, the data-stream generation routine  310  outputs the record to the stream as a spatio-temporal tuple in step  612 . In step  614  the pointer moves to the next record, then flashes the output record from the buffer table  306  in step  616 , and returns to step  608 , which is the start point of the inner loop. 
         [0068]    Referring next to the flowcharts in  FIGS. 7 and 8 , the process is described of the temporal joining operator  312 . 
         [0069]    The flowchart in  FIG. 7  is the process of input from the data-stream generation routine  310  to the temporal joining operator  312 . Specifically, the output in step  612  of  FIG. 6  is input as a spatio-temporal tuple and is stored in a combining operator in step  702 . 
         [0070]    The flowchart in  FIG. 8  is the process of input from the by-channel ratings compilation operator  308  to the temporal joining operator  312 . In step  802  of  FIG. 8 , the temporal joining operator  312  obtains a spatio-temporal tuple that satisfies a matching condition in the combining operator. Here, the matching condition is a condition written following match: in the following code example: 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 stream&lt;Combined_tuple&gt; Join = 
               
               
                   
                 TemporalJoin(Input_stream: T_stream) { 
               
               
                   
                 param 
               
               
                   
                 match: Input_stream.CH = T_stream.CH 
               
               
                   
                 } 
               
               
                   
                   
               
             
          
         
       
     
         [0071]    In step  804 , the temporal joining operator  312  determines whether the term of validity of the matched spatio-temporal tuple is valid at present, and if valid, combines the data in step  806 . 
         [0072]    If the term of validity of the matched spatio-temporal tuple is not valid at present, the temporal joining operator  312  performs exception handling in step  808 . Examples of this exception handling include discarding an input stream without executing the combining process, repeating the process of the flowchart in  FIG. 8  from the beginning after waiting for a designated time, and if the data isn&#39;t combined after iterations, outputting an error log. 
         [0073]      FIGS. 9 and 10  are diagrams for explaining the advantages of the present invention in more detail. Specifically, in a conventional technique schematically shown in  FIG. 9  in which there are three databases  904 ,  908 , and  912  on which the process is performed of joining with an input stream  902 . An output is finally obtained by inputting the stream  902 , thereafter performing a process  906  for joining the stream  902  with the database  904 , a process  910  for joining it with the database  908 , and a process  914  for joining it with the database  912  in sequence. Such a serial joining process obviously takes much time. 
         [0074]    On the other hand, in the process according to an embodiment of the present invention, schematically shown in  FIG. 10 , the process of generating a buffer table from a database  1004 , in addition to an input stream  1002 , to perform a temporal-stream generation process  1006 , the process of generating a buffer table from a database  1008  to perform a temporal-stream generation process  1010 , and the process of generating a buffer table from a database  1012  to perform a temporal-stream generation process  1014  can be executed in parallel. They are joined together in a joining process  1016 , thereby allowing an output to be obtained at high speed. 
         [0075]      FIG. 11  is a diagram of an embodiment in which the present invention is applied to a road congestion pricing system. 
         [0076]    In  FIG. 11 , a traffic stream  1102  is a stream of information on vehicles passing through a toll road and includes a vehicle ID (CarID), a road ID (RoadID), and time (Timestamp). A road toll database  1104  includes a section ID (RoadID) of a section passed through, a start time (Start) and an end time (End) of the block time of the section, and the toll (Fee) for the section. 
         [0077]    According to the embodiment of the present invention, a buffer table is created from the road toll database  1104 , and a spatio-temporal toll stream is generated. The toll stream includes data on a validity start time. The road toll is determined by a simulation or the like which depends on the RoadID of a section passed through and the congestion level of the section during immediately preceding x minutes, and a time block to which the toll is to be applied is determined. 
         [0078]    A toll determination operator  1108  inquiries a road toll based on the arrival time of the car and the ID of the toll road by using the traffic stream  1102  and the toll stream from the road toll database  1104 . A billing operator  1110  charges each car with the road toll obtained by the toll determination operator  1108 . The history thereof is stored in a billing history database  1112  as the need arises. 
         [0079]      FIG. 12  shows another embodiment of the present invention in which the system is applied to a stock ordering process under temporal restriction. 
         [0080]    In  FIG. 12 , a stock price stream  1202  includes a tuple of a stock ID (StockID), a stock price (Price), and time (Timestamp). A buy-order database  1204  has order ID (OrderID), stock ID (StockID), user ID (UserID), stock price (Price), and duration (Duration) fields. 
         [0081]    A buy order stream  1206  is a stream of the data of the buy order database  1204  using a buffer table. 
         [0082]    An order determination operator  1208  performs sequential matching of the stock price stream  1202  with the buy order stream  1206  in terms of a stock price (Stock.Price&lt;=Order.Price) and outputs a matched Order ID. 
         [0083]    An ordering operator  1210  orders a stock with the order ID output from the order determination operator  1208  and records the result on an ordered-stock database  1212 . 
         [0084]    Although the embodiments of the ratings compilation process, the road congestion pricing process, and the stock ordering process under temporal restriction has been described, the present invention is not limited thereto and can be applied to any examples in which a spatio-temporal database stored in a hard disk drive or the like and stream data are joined. 
         [0085]    The present invention can be implemented in any computer systems or platforms other than those in Java® used in the above embodiments.