Garo Garabedyan- a private blog

Information technology research

Contents:

1. Abstract. Where tables are used

2. The Algorithm in a few words. Understanding how tables care information

3. Addressing cells. Setting calling names of cells in order to extract information

4. Semantics and value of secondary cells

5. The Algorithm in deep. Theoretical translation of tables into natural text statements

6. Constructing new tables (using MapReduce’s idea). Comparison with SQL queries

7. Legal Drinking Age in Asia. Table to natural text translations

8. Is Semantic web a table like model

Understanding meaning of main cells and secondary cells in a table and deriving meanings in order to present tables as natural language sentences (search-able by machines). Querying this data and receiving as a result a composed table by the search engine.

Free text to table is a possible future option.

I believe that the table is able to be translated in natural language sentences in order to understand and index the information as a natural text by search engines. Browsing the web we find tables explaining time schedules, steps, categories and so on. May be the table is the second most popular form of expressing information next to the simple text (array of characters and symbols).

The Algorithm in a few words. Understanding how tables care information

Data in tables is presented in two main cell groups, the first group is the main cells which carry the general attributes of the data and the second is the group about the concrete category/ case (in variation tables). This two groups are in most of the real life tables separated by their formatting, data type of content and place in the table’s rows and columns.

Understanding the way this cells content relates to each other and translating this relations into natural text sentences like data structure which is able to be queried like a relational database table.

By using of a MapReduce (http://labs.google.com/papers/mapreduce.html) like algorithm, new tables can be created from the database of many tables to present search result by mapping equal cell names or values according to a complicated user query search.

This is an example of a table aiming to present all possible combinations of a structure of a table.

Table 1. Theoretical table presenting all important cell arrangements (carrying information about the content of the cell according its arrangement)

One of the possible ways to address cells is to begin setting names from the upper left cell, but the other which I find as more practical is to start from the most lower and most right cell. I prefer the second way because the most common tables have main cells on first (and second) row and/ or first row and first column, so it is very possible if you start with the upper and most left cells to find a cell, which is separating going deep in the table (if table contains more than one main cells row or column). For this reason in order to not name and later address cells like: R3a, C4a. Lets begin from the most low and right cell.

The above consideration does not reflect to the algorithm itself but rather to the more rational naming of cells which rationalization enables easy white box testing and debugging.

Semantics and value of secondary cells

Table 2. Scheme of semantics and values of a cell. The bottom right cell is a secondary cell with semantics: semantic1, semantic2 and value: values1

Values can be these data types:

number (if a space character, new line character if found it is ignored)

number range (spaces are ignored, “-” and “,”/”;” between the numbers describing the range)

picture (the “alt” text if it is set can be treated as value)

href

Note: Ignore comments (i.e.:“18 (<string>)” is not string, but number). Comments are used with this patterns: “<statement> (<comment>)”; “<statement> - <comment>”; “<statement> <- <comment>”. Spaces are added only for a better visual expression. Of its own the algorithm ignores them from the very beginning, except the statement is string.

The Algorithm in deep. Theoretical translation of tables into natural text statements

All cells are addressed and main cells are recognized from the rest. The above theoretical table (Table 1) is used in order to present the all important policies of the algorithm.

R3; C4a and R3; C4b are split cells. R4; C2,3 is a merged cell (by columns). R5,6; C1 is a merged cell (by rows), too.

There is no difference in split cell by row or column. I do not find any reasonable application of this two different kinds of splitting instead of splitting by diagonal (by column and row at once) of the upper right cell.

Every secondary cell is translated into a natural text statement, by this pattern:

[R2; C2] are/is (R2; C2)

are - if main cells are more than 1

is - if there is only one main cell

R2; C2 – the cell itself

(R2; C2) – the value within cell R2; C2

[R2; C2] – the value(s) of the main cells of R2; C2. The semantics of cell R2; C2

Constructing new tables (using MapReduce’s idea). Comparison with SQL querie

Having many secondary cells collected from many tables from different domains around the Internet is enough data to construct a new table as a result every time a query is executed. Secondary cells contain in themselves information about the semantics and about its value. Constructing a table as a search result is useful when the database does not contain a suitable table for the search query, but many columns and enough rows from different tables solely extracted can satisfy the search. Secondary cells’ semantics and data types of their values are not unique, many tables represent one and the same phenomena. By using some NLP policy is possible to claim is a secondary cell semantics equal to others secondary cell semantic from a different table.

User search can be treated as a query for a set of secondary cells with specified semantics and a specified value(s) for a semantic(s) which have to be bound with the presented results.

Table 3. Search query presented in a table

Result:

The Lowest 10 Prices are: price1, price2, price3 // there are supposed to be MP3 Players on a same low price, but I have not deal with this possible case, this is just an example

Alternatives on Price price1: vendor1, product1, priceX1; vendor2, product2, priceX2

Alternatives on Price price2: vendor3, product3, priceX3; and all the above

Alternatives on Price price3: vendor4, product4, priceX4; vendor5, product5, priceX5; and all the above

As a comparison with SQL queries and the relational Database theory. I think that this are queries just like SQL ones executed on a relational DataBase but here we have no FROM clause, so the engine searches everywhere he finds such columns’ semantics and uses its rows if possible to do so. This kind of searching is made on the base of multiple searches for intermediate values associated with the same intermediate semantic around this mass storage of tables.

Examples of query type searches which can be performed better if the above is implemented:

What is the population in USA in 1979 and which countries have a similar amount of citizens?

How much does it cost a Sony mp3 player and which are the alternatives on the same or lower price?

How long does it take to travel from LA to San Francisco by car and is there other so big or bigger (in meaning of citizens) city where I can go from LA in a shorter traveling time again by car?

Of course, these are not general search queries according to the level of Natural Language Processing capabilities of search engines. This queries are at all executed by a specific domain related user interface. But I believe that if every result is serialized to tables this approach can be extremely useful.

Many data analysis can be made on the base of such search queries.

Is Semantic web a table like model

Semantic web is a declaration between the HTML in general code and the information semantics behind the HTML (in microformats and RDFa). This can be presented as a link between the semantic and the concrete technical presentation of the semantic.

This semantic web links (semantic tags and pieces of HTML as values) are not table like, it is hard to compare the values of the semantics because they are different and are closely related to the technical representation.

Attachments to Querying Tables in the Web

Table of Legal Drinking Age in Asia

“De jure” column is the reason this table is presented as a real life example. “De jure” column contains a table with two main cells placed on its first row- “Drinking Age”, “Purchase Age”. This main cells head two columns which are sometimes merged.

Nowadays results of current search technologies

I have queried Powerset (http://www.powerset.com/) and received these results:

Screenshot not available here. See the printable version of the document.

Screenshot 2. Search results from Powerset on “what is the legal drinking age in Armenia”. With red color are surrounded important text snippets.