Showing posts with label searching. Show all posts
Showing posts with label searching. Show all posts

Tuesday, June 17, 2008

to boldly go....

For sure, there are a lot of nice little visualisation tools for flickr and even more has been written about tagging, folksonomies, and web 2.0 search (including the 'flickr!' article in this blog...). Nevertheless, I found a new flash-based application for flickr tag / search visualisation that is worth while taking a look: The Tag Galaxy.

Tag Galaxy visualises the search process in a bold star trek manner. Your search keywords (tags) are shown in a central star/planet with related tags spinning around it. you can refine your search by clicking on one of the small tag planets. This is only a one step ahead search...why not showing related tags of related tags....with according interrelationships...? Sounds weird? Should be worth a shot. Clicking on the central star/planet guides you to another view, where the search results (images) are shown on an animated globe. Really neat....and interesting what comes out if people have enough time to play around with flash ;-)

Anyway, the trouble with neat search visualisations often is that the visualisation is nice to look at but it gets boring after a few tries. Real good visualisation gives you more information than without the visualisation. Only if its worth while, you will keep on using it. Just think of Google Maps. Your search related with geographical information always improves your search results...and thus you will also use it next time....

Wednesday, August 29, 2007

Combining Social Networking and Traditional Web Search

We are already waiting quite a while for Google (or Yahoo) to incorporate social networking technology into their web search services. Personalization of search results (as already being offered -- of course in some limited way) as a very first step towards the right direction has become part of traditional web search. The next step should include not only search results from personal resources but also from resources being available within your personal social network. Seems to be straight forward...?!

First thing, include all resources that I have tagged (you can also distinguish between resources that are yours and resources owned by others that you have tagged). In addition to the traditional hyperlink graph of the web (as it is used by the PageRank algorithm), new (weighted and labelled) arcs have to be inserted connecting your homepage (site/blog or whatever) with all the resources (own and foreign) that have been tagged by you.
Ok, now let's consider that everybody's tag-links are inserted into the hyperlink webgraph. Next thing is to insert (weighted and labelled) arcs from your homepage to the homepages of all your friends (according to your personal social network).
You will end up with a graph that includes (a) traditional hyperlinks, (b) personal tagged + weigthed links to resources, and (c) personal tagged + weigthed links to other users. This composite social webgraph should be sufficient for extending the traditional PageRank algorithm to include social networking information.
Of course (and I'm pretty sure of that and I don't go into details now) a lot of adjustments concerning the weights and the use of tags/labels for indexing have to be considered. But, I think it should be possible...

To some extend, a similar approach has been implemented by lijit. lijit is a personalized search engine that makes use of all your available social networking information. At registration, besides your homepage (or blog ... unfortunately you can not manage several different blogs) you pass over your username for several bookmarking/social networking services as well as the URLs of (a) content provided by you and (b) websites (blogs) of your friends. lijit creates a searchable webgraph covering all the resources and networking information that you have provided. Therefore, searching with lijit comes close to a rather personal variant of searching your very own web-universe.

Social Graph Based Search is also the topic of a video podcast from Scobleizer. Although I can't follow his argument that the social networking companies will kick Google's butt in four years (he states that Google's PageRank algorithm cannot be adapted to include social networking information...at least not in a way scalable for Google's purposes and also not with the current business modell of today's SEOs [=Search Engine Optimizers]), I agree to the way how to include social networking information into traditional web search.

Tuesday, May 15, 2007

Next Generation Search Engines revisited...

As reader of my blog for sure you know that one of the main topics is (semantically enhanced) searching the web. Recently I was rereading Andrei Broder's short paper on 'A taxonomy of web search'[1], where he was also referring to the three generations of web search engines. His article dates back to 2002. Environment and technology in the web are rapidly changing. So, what about this three generations? Do we already need a 'next generation'? And what about the discussion about 'Search 2.0'?...
But first, let's recall the three generations according to Broder:

  • First generation: search engines are useing almost only on-page data such as text and formatting information to compute result ranking (1995-1997, cf. Alta Vista, Excite, etc...).

  • Second generation: search engines are using off-page, web-related data such as link analysis, anchor-texts, and click-through data (1998-..., cf. Google).

  • Third generation: search engines try to blend data from multiple, heterogeneous sources trying to answer 'the need behind the query'. The computed results are customized according to the user's information needs, taking into account the user's personal data background, context, and intention (now? - ...).

Clearly, search engines of the third generation include social networking information, tagging, user feedback, semantic analysis, recommendations, and trustworthyness of information (according to its source).
In read/write web the topic is also addressed as comparison of traditional search technologies with what they call 'Search 2.0' [2]. As usual, I don't like the 2.0-term. What is discussed there, refers to Broder's definition of 'Third generation' and adds nothing significant new to it (besides the marketing term). But, the article is definitely worth reading, because a lot of recent search engines are referenced and discussed (and also because of the interesting discussion that follows). They distinguish between 'Finding' information and 'Discovering' information, while relating the second term to 'Search 2.0'.

Broder distinguishes different sorts of web search queries:

  1. Navigational: intented use is to reach a particular web page (similar to 'known item' search in classical information retrieval). Therefore, navigational queries usually do have only one 'right' result.

  2. Informational:
  3. intended use is to acquire information assumed to be present on one or more web pages (as in classical information retrieval).
  4. Transactional:
  5. intended use is to find a web page, where further transactions (e.g. shopping) will take place.

If we take social bookmarking services, navigational queries can be computed simply by using the user's personomy (i.e. the set of all tags used by a distinct user). If the goal is to find a web page, which has been already accessed in the past, the page might be found quickly, if the user has registered the page within the bookmarking service (which comes to 'Finding' information). But, the query might also be resolved by using other people's tags, if somebody has tagged the page (with objectively descriptive tags).
Social bookmarking services are also usefull for the other two purposes. In addition, if the page is found, the social networking information can be utilized for 'discovering' new, previously unkown, but related (similar) information (which comes to 'Discovering' information). Hotho et al. present an adaptive ranking algorithm (FolkRank) for social bookmarking systems and discuss the problems that arise for tag-based search engines [3].

But, to answer the 'need behind the query' as Broder states in his definition of 'Third generation search engines', further personalization is mandatory. Only, if the search engine is able to find out the context of a query w.r.t. a given user and a given situation (i.e. even the same user might have different information needs in different situations), then it is possible to grasp the actual context of the query, and thus, also the 'need behind the query'...
[to be continued]

References:
[1] Andrei Broder: A taxonomy of web search, SIGIR Forum 36, pp. 3-10, 2002.
[2] Ebrahim Ezzy, Richard MacManos: Search 2.0 vs. Traditional Search, read/write web, June 20th, 2006.
[3] Andreas Hotho, Robert Jäschke, Christoph Schmitz and Gerd Stumme: Information Retrieval in Folksonomies: Search and Ranking, in Proceedings of the 3rd European Semantic Web Conference, pp. 411-426, 2006.

Friday, April 13, 2007

Tag search vs. keyword search......substitution or complement


As you know, collaborative tagging systems (CTS) have become rather popular Web 2.0 applications (although I don't like the term 'Web 2.0'...please use 'Social Web' instead). A CTS allows each registered user to maintain her own tags that add semantic annotation to corresponding web links. Today, 'tags' are simple unformatted text data. Tags are transporting meaning, i.e. semantics. Because the user is free to choose any text string (symbol) for a certain semantics (concept) related to a given resource (web page or object). To communicate this semantics, two or more users have to agree upon using the same symbols denoting an object (remember the semiotic triangle [1]).

First difficulty is syntax: there are several posibilities to write a word (of course not all of them are necessarely correct or not all of them belong to the same language). The problem becomes even worse, if one tries to combine several words in a single string (how to separate words?...use CamelCase, underscores, blanks, ...).
Next comes language dependent problems such as polysemy (homonyms or synonyms). For homonyms we have the same symbol but different meanings, and for synonyms vice versa.

Syntax and language dependent problems alone cause tag based search to be more difficult to handle than traditional keyword based approaches (by keyword based approach we refer to full text search or keywords assigned to the resource by the resource author or by some designated expert). For full text search, a query string given by the user (or at least its word stem) has to match some string being part of the searched resource. Keywords given to a resource by some designated expert should meet some level of objectivity and thus, a user might be able to 'guess' the keyword while thinking of a well suited query string. Keywords provided by the author refer to her specific point of view (same with tagging). These 'subjective' keywords are much harder to guess for the arbitrary user, because she does not necessarely share the same context with the (tag) author.
In CTS we distinguish several distinct categories of tags [2]. Among others, there are two fundamental different tag categories: descriptive tags and functional tags. Descriptive tags refer to more objective tags, tags that are used to describe a resource in some general maner. Functional tags on the other hand do include an intended functional use esp. for the tag author and thus, are more subjective. While descriptive tags serve better for general web search, functional tags are useful most for their authors, but not for other users.
To analyse the benefit of tagging for web search, we have to take into account that many users are providing tags for a specific resource. Depending on the distribution of the tags attached to a specific resource, one can observe a power law (see also [2]). Few tags are used very often, while most of all the tags attached to a resource do occur only scarcely. Those few tags rather often can be identified with descriptive tags, while the so called 'long tail' of the other tags often belong to the category of functional tags.
So, how can we make use f that fact?
In [3] the authors propose to use tags for search query refinement. For that reason, they distinguish between two defferent categores of tags (that do not necessarely correspondent with descriptive and functional tags). They distinguish search keywords as being the most popular tags assigned to a resource, which can help to increase the hit rate if being used for query refinement, and exploration keywords, which cannot. Because exploration keywords reflect the personalized search context and information need of an individual user they are supposed to be helpful for the exploration process.

Monday, February 19, 2007

LEARNTEC, Karlsruhe February 13-15


This year, we participated at the LEARNTEC Fair in Karlsruhe (February 13-15). LEARNTEC is focussed of e-learning technology integrating universities and industries together within an exhibition and a congress. As officially being the advisor of an ESF/BMBF funded startup company called OSOTIS, I was visiting my students who took part at this exhibition. OSOTIS is also the name of the 'Academic Video Search Engine' that serves as a testbed for our research in semantic web and multimedia search technology.

The setting of OSOTIS is the following: We are dealing with lecture recordings and offer a search service over and also inside those lecture recordings. The main advantage of OSOTIS is that most of the video post processing that is necssary for implementing a search is done in a completely automated way. Many other video search systems depend on cost intensive post processing, such as segmenting the videos into short 'learning objects', manually annotating the video segments, etc.
OSOTIS is different:
It makes use of additional information resources such as desktop presentation (e.g. powerpoint or pdf slides or simply desktop recordings) that can be synchronized with the video recording in different ways. If there is only a lecture video without any additional information source, even speech recognition technology is able to provide keywords that can be used for the video annotation. In this way, the video can be automatically segmented and the segmants can be annotated with keyword descriptors. Additionally, if there is no way to determine the content of the video, OSOTIS offers manual annotation and social tagging services to all registered users. Thus, there is always some way to search inside each lecture recording, no matter if additional information resources are available or not.
You just enter a keyword and OSOTIS will display a list of lecture recordings that are related to that keyword. By selecting one of the results, the video will start at exactly that point in time that is directly related to the user query. OSOTIS does not host the video resources on its own server, but offers only links to the original streaming servers (for streaming resources) or origin servers with podcast/videocast recordings. Thus, also all kind of video formats can be maintained, as e.g., real media, mpeg, mp4, flash video, and others.
Up to now, the main part of hosted video lectures is in given in German (and thus being hosted by german speaking universities, as also Austria or Switzerland). But, the number of lecture recordings in English will be increased soon.

Thursday, December 21, 2006

Semantic Search ... confusion ahead


When I was attending a talk of Thilo Götz on UIMA, the word came to 'Semantic Search'. Up to that point in time, I was quite sure about the meaning of this term. But, I had to realize that several people think in different ways about it.
As far as I have understood the meaning of that term, 'Semantic Search' refers to all techniques and activities that deploy semantic web technology on any stage of the search process. Thilo Götz (and he's not alone with that) refered to 'Semantic Search' as a 'traditional' search engine that is using a semantically enriched search index (i.e. a search index that incorporates ontologies or information/relationships infered from ontologies).

From my point of view the later definition refers only to a part of the whole process. Let's take a brief look at search engine technology: You have to consider the index generation (including the crawling processes, information retrieval for creating descriptors, inverse indexing, overall ranking, clustering, ...) as well as the user interaction (including query string evaluation, query string refinement, visualization of search results, navigation inside the search domain), not to forget personalization (concerning a personalized ranking of the search results including some kind of 'pre-selection' according to the personal information needs of the user, a personalized visualization, etc.) -- which will become of much more importance in the nearby future.

But, to generate a semantic search index there are several possibilities to consider:

  • Using unstructured web-data (html, etc. ...) in combination with information retrieval techniques to map the information represented in the web-data to (commonly agreed) ontologies of well defined semantic.

  • Using semi-structured web-data that already include links to well defined ontologies (being commonly agreed upon or at least being mapped to som standard ontologies).


For both steps, the generation of a semantic index requires more than just compilation of the retrieved data. Although the index might contain unstructured web-data including ontologies of well defined semantics, the main purpose of the index is to provide fast access to the information being represented in it. To generate the answer for a query, the search engine simply does not have enough time for performing logical inferences to deduce knowledge (a.k.a. answers) online. Of course, this (logical inference) has to be deployed beforehand (i.e. offline), just in a similar way as the computation of today's pageRank.

So, what is the use of machine processible semantics in a search engine's index data structure? The following possibilities can be considered (the list is open for additional suggestions...):

  • to add new cross-references between single index entries (associations),

  • to find similarities between index entries ( = web data) w.r.t. their content, and

  • to discover dependencies between single index entries to enable
    • better visualization of the retrieved domain of information, and also

    • efficient navigation to better fulfill the users information needs.


  • of course also to disambiguate and to cluster web-data for better precision and recall (this is already done with current IR techniques).


To compile a semantic index, also the crawling process has to be considered. While the primary goal of a web crawler is to gather as much web-data as possible as fast as possible (and of course to maintain its level of consistency), a 'semantic' web crawler besides unstructured web-data also has to look for semantic data, as e.g., RDF and OWL files, and also for possible connections between unstructured web-data and semantic data. For crawling RDF or OWL, a traditional crawler has to be modified. While the traditional crawler just analyzes the HTML data for link tags, RDF and OWL don't contain link tags but they often include several namespaces that determine new input for the crawler. Besides mere data gathering, the crawler should also preprocess data for being included within the index. This task often is implemented as a separate step (and denoted as 'information retrieval'). But, it influences the crawlers direction and crawling strategy and thus, also has to be considered here.
Web crawlers often are implemented in a distributed way to increase their efficiency while working in parallel. New URLs found in the web pages being crawled can be arranged according to the location of their domain (geographically). In this way, an instance of the distributed crawler receives only new URLs to be crawled that are located in the same (or a nearby) domain. The same argument holds for the resources that are to be crawled by semantic web crawlers. But, for semantic crawlers, also the (semantic) domain of the crawled data might be of importance, e.g., an instance of the distributed crawler might be responsible for crawling a specific domain (=topic) or only domains that are (semantically) closely related to the domain of interest.


For the semantic search engine the compilation of an index from the web pages being delivered by the crawler differs from the compilation process of the traditional search engine. Let us first recall the traditional index compilation process (for text related data, i.e. this does not hold for multimedia data such as images or video clips):

  1. resource normalization, i.e. all resources that contain explicit textual content have to be transformed into text files

  2. word stemming, i.e. transform all terms of a retrieved and normalized web-document to their word stems

  3. stop word removal, i.e. cut out all terms that are not well suited for identifying the processed text file (i.e. that are not suitable as descriptors). Often only nouns are taken as descriptors (this can partly be achieved by applying pos-stemmers (=part-of-speech stemmers).

  4. black list processing, i.e. terms that for some reason do not qualify as descriptors are cut out.


This process results in a list of descriptors that describe the web-document being processed. For each descriptor a weight according to its descriptive value for the text file has to be calculated (e.g., by term frequency - inverse document frequency (tf-idf) or other weigth function). The table resulting from combining the weighted descriptors with their underlying web-documents constitutes the index. By inverting this index a descriptor delivers all related web-documents in combination with their pre-calculated weight function (that determines how well a given descriptor is suited to describe the content of the according web-document). To increase precision and recall, the general relevance of the web-documents can be computed beforehand (i.e. nothing else but the Google PageRank).

For a 'semantic index', metadata (such as, e.g., ontologies) have to be taken into account and be combined with the traditional index...

...to be continued