Thursday, September 18, 2008

Uniform Search – An intelligent and better search on sorted data

Copyright (c) 2008 by Gagandeep Singh
This material may be distributed only subject to the terms and conditions set forth in the Open Publication License,
v1.0 or later (the latest version is presently available at http://www.opencontent.org/openpub/).

I appreciate the concept of binary searching, divide and search. It gives significant boost over linear search. It gives searching more natural look, i.e., it search resembles more like human beings’ searching, but not exactly the same. And we know that we can search faster than machines. Oh, I really don’t mean by time wise but the number of passes machine took to complete the task and number of passes we took to complete that task. What I really means that some humans are really smarter than the machine, because they can learn and bettered that approach.

Now come to complete off track from previous one. What happened in the history? I really don’t know. But assume that we shed all our weapons of innovation to the great searching (binary search) and concentrate more on sorting and sorting & searching mixed (binary search trees, B-trees, B+ trees, etc.). We do things that were fascinating but forget to provide basic foundation right. Oh! You want to hit me because of that line. Just hit me. Because time needs change and we cannot stick to old chair, if it was crumbling. If you do that then you are only responsible for results, don’t blame me for that. I am very irresponsible person, who makes furniture with an axe. I just do things. Team has plans. Professionals have plans. Organizations’ got the plans. They're schemers. Schemers trying to improve their little worlds. I'm not a schemer. I try to show the schemers how pathetic their attempts to improve things really are. So... When I say that I’ve better method than binary search. You know that I'm telling the truth.

Now get into real business. The method of new searching called Uniform Search. Because it assumes that data is uniformly distributed over the entire interval. And based on that determine where the intermediate element should be. In binary search intermediate element always in middle, but in Uniform Search based on lower value, upper value, and number of elements intermediate element is decided. This concept is more like Humans, o.k. as far as I am concern and I believe that I am Human. If I had a book, definitely I had, with 1000 pages and 10 chapters and need to open 3rd chapter. Then I open page number 201 first. Assuming uniform distribution, it means that every chapter took 100 pages. And if it is 7th chapter then according to so called uniform distribution, that is certainly not here, the 3rd chapter is between 1 to 200 pages and 1 to 7 chapters. So, it must be somewhere

(200/7)*3=600/7=85(floor value of 85.71)

Hence, I now open page number 85. May be I am lucky to find the chapter, but surely I am tired to carried on this example.

But, one thing you would like. The comparison between Uniform search and binary search:

Comparision between Uniform Search and Binary Search
Comparison between Uniform Search and Binary Search
This graph show how data of 100 numbers searched for each number in the data list. And it plots number of passes of binary search and uniform search.

You can download the program fragment Uniform Search.



Sunday, March 2, 2008

DeepAILU :'Deep Artificially Intelligent, Like You'

Hi, Everyone may be you are wondering what that word DeepAILU actually refers to. That word refers to 'Deep Artificially Intelligent, Like You'. 'Like You', here refers to Humans like you and me. I know, what I am now writing may be looking weird to some, but I suggest read whole article, then you may find that DeepAILU might be possible with current capabilities.

Like Human, Machines also have Intelligence just with three-step process. And the process is,
.Collect the relevant data.
.Process the data, to make algorithm (function) out of it.
.Use that algorithm to predict future values.


Let us understand this process. How humans react to situations.

Firstly, Humans check whether that situation is similar to any previous situations, if that is the case then they retrieve the action taken at that time and result of that action (fruitful or not). For example, if you have to go over some place then your brain retrieves information about that place from its database. The relevance of information might be depend upon whether you already gone there or not. If you not already gone there then the information might be, how far that location is. Moreover, from that distance and location your brain search for how to reach there, by bus, by car, by train, by plane, etc. Might some more details also searched by your brain. If you gone there already and frequently, then your brain retrieves information about that that might be mode of transport you prefer, the average time taken by that mode, etc. If you gone there already and infrequently, then your brain retrieves information about your mode of transport at that time and what was result of that journey, according to what you expected or not. In the end whatever transport mode you chose, whatever route you chose, wherever the journey leads to will be in your mind, for next reference. That is the first step, in the three-step process, collects the relevant data from your experience, from your seeing, from your hearing and from all your senses. Senses are humans input devices; the sixth sense is virtual device in which brain extract information from mind and gives humans input.

Second, Humans always resist to change, why? Because when humans are used to situations then their brain already developed algorithms to react to that situations. In other words, your brain already knows actions associated with the situations. That actions generally referred by Human beings as ‘used to’. This means, when you are used to situations that mean your brain already built an algorithm to react to that situation. Let once again try to understand the concept by an example. When you joined an organization, for the first time, then every thing seems alien to you. That means your brain not familiar to what called culture or atmosphere of the organization. Moreover, when you spend some time there, then you should most probably used to that organization’s atmosphere and ethics. That means your brain made algorithms to tackle most routinely works of organization, might be your brain not able to algorithmize all the tasks, but only significant amount of routine algorithms necessary for sustainability in any organization. However, some like me might not be able to ‘used to’ culture that means our brain not easily programmable. In the process of learning organization’s ethics, you might be enjoying the changes that brought to you by management. However, what happens when something changes when you were used to routines and ethics of organization, for example, your friend leave job unexpectedly, your manager changes, your junior perform better than you, etc. In these changes, your brain tells you to works like previously and eventually you do it, but if the output it produces, was not as previous, your brain try reconfiguring itself that is new algorithm was building now. And brain always escaping from making new algorithm and erasing previous one. It usually tries to escape from heavy work related to discovering new algorithm. Because every discovering of new algorithm involve referring to all related parameters (or situations), which involves heavy works (I discuss that in later writings). Therefore, brain tries to algorithmize everything and tries to avoid, if avoidable. That is the second step, in the three-step process, Process the data, to make algorithm (function) out of it. Algorithm making description is vast field in itself, so my brain escape from it this time and says that do it other time :). Therefore, you have to wait until I post some other article. I do I promise.

Third, Humans always visualize things. But how? They always visualize the things they previously encountered. May be you don’t agree with me, you might thought you can visualize other things also. In that case, you might forget about the sixth sense, which is virtual device in which brain extract information from mind and gives humans input. Never under estimate this virtual device this is most powerful device, which makes us Humans that is it gives power of estimation, the estimation of unknown or unseen things. It gives what you say intuitive to you, the intuitive things comes from the algorithm and data you already have. In childhood, I feared of ghosts, because I listen about them and watch horror movies. Therefore, I have idea of what ghosts were and how deadly they are and they always came in night. In nights, I often visualize certain unknown or unidentified things as ghost that what my brain interpret those certain unidentified things. How brain does that? Because brain already developed the abstract picture of ghosts, so it maps certain unidentified things to ghosts. This happens most in the night when I watch a movie, listen to story about ghosts, or think over movie or story or ghosts. Hence, my brain use already created algorithm to predict future values or to visualize unidentified object. What can I say about this brain it predict thing, if you cannot able to see the things. When you drive in semi-dark (may be due to faulty light condition or whatever the reason might be), then your brain some seen things and try to predict other things on road. Might be this predicted value wrong might be right but brain predicts it (I feel sorry if your brain fails to predict right values and whatever happen). Nevertheless, we reach our third step of three-step process, that is our brain use already created (or may create at that time also) algorithm to predict future values.


Hence, you know the secret of how brain works in respect to public of 20th century but I guess you are from 21st century, you love technology and might be I am too that’s why I am writing this. Therefore, you need some technological feasibility aspects also. I want to implement DeepAILU and of course, it is an open source project, but the timeline not thought over yet. The language of implementation might be any object oriented language with persistence object support. However, the real dilemma is not here, the dilemma is there are not even technological advancements in subordinate areas. For example, the datamining field, Natural Language processing (NLP) the identification of objects in video or image, the audio capabilities (sound identification, etc) is also not sufficient for DeepAILU. Hence, let’s wait for my next articles or blogs whatever that suggest the advancements in these areas. As you know, I have to think a lot so the wait time might took a while but never forget me. I will definitely back....

Comments are welcomed