Software Troubles and Troubleshooting

Jailbreaking and deploying on iphone3gs using ios5

2012-01-22T13:46:00.001+05:30

First jailbreak using latest version of redsnow :

http://osxdaily.com/2011/12/27/how-to-jailbreak-ios-5-0-1-untethered-with-redsn0w/

Then follow these instructions to run/deploy your app on your iphone :

stackoverflow.com/questions/246422/how-can-i-deploy-an-iphone-application-from-xcode-to-a-real-iphone-device

Installing node.js on hostmonster/bluehost

2012-01-20T16:29:00.001+05:30

http://rcrisman.net/article/10/installing-nodejs-on-hostmonster-bluehost-accounts

While installing git you many want to get the latest source from http://git-scm.com/download

Oracle finding columns

2011-12-09T11:58:00.001+05:30

  finding columns
 Find all tables that have at least one column that matches a specific PATTERN in the column name

 SELECT       TABLE_NAME,       COLUMN_NAME    FROM       ALL_TAB_COLUMNS    WHERE       COLUMN_NAME LIKE '%PATTERN%';

iphone courses online

2011-12-08T16:44:00.001+05:30

iOS programming resources online ;

http://teamtreehouse.com

http://itunes.apple.com/in/itunes-u/ipad-iphone-application-development/id473757255

for ios 5 :

http://itunes.apple.com/in/itunes-u/developing-apps-for-ios-hd/id395605774

Enabling sudo on mac os/Enabling root user on mac os

2011-12-07T23:24:00.001+05:30

http://www.spy-hill.com/~myers/help/apple/EnableRoot.html

who is locking whom oracle locks

2011-11-25T14:35:00.001+05:30

select s1.username || '@' || s1.machine
|| ' ( SID=' || s1.sid || ' ) is blocking '
|| s2.username || '@' || s2.machine || ' ( SID=' || s2.sid || ' )
' AS blocking_status
from v$lock l1, v$session s1, v$lock l2, v$session s2
where s1.sid=l1.sid and s2.sid=l2.sid
and l1.BLOCK=1 and l2.request > 0
and l1.id1 = l2.id1
and l2.id2 = l2.id2 ;

Oracle alter table add or drop column

2011-11-17T15:59:00.001+05:30

alter table supplier drop column supplier_id;

alter table
cust_table
add
cust_sex varchar2(1) NOT NULL;

Her is an example of Oracle "alter table" syntax to add multiple data columns.

ALTER TABLE
cust_table
ADD
(
cust_sex char(1) NOT NULL,
cust_credit_rating number
);

Oracle add or drop primary key

2011-11-17T15:52:00.001+05:30

ALTER TABLE supplier
add CONSTRAINT supplier_pk PRIMARY KEY (supplier_id);

ALTER TABLE supplier
drop CONSTRAINT supplier_pk;

Installing XCode/IOS Simulator on Mac OS 10.6.1

2011-10-17T00:35:00.000+05:30

First you need to upgrade your Mac OS.
Click on the Apple Icon -> Software Update and follow the instructions.
In my case it downloaded 1.33GB of updates.
First time it wasn't downloaded correctly so it asked me to download again.
I did that and restarted and I had been moved to Mac OS 10.6.8.

Then I installed the .dmg file for iOS SDK(4 GB). Instructions.
So, in all, I ended up downloading 7GB of data just to install XCode on my MAC. Amazing !

Downloading iOS SDK from command line through wget

2011-10-16T01:23:00.001+05:30

1. Install Export Cookies Extension for Firefox.
2. Login to iOS Dev Center and start downloading the file, after a
while cancel the download.(from the Downloads Window, get the download
URL)
3. Export cookies to cookies.txt
4. Upload cookies.txt to the server where you want to use wget.
5. Login to your server and :
wget -U firefox -ct 0 --timeout=60 --waitretry=60 --load-cookies
cookies.txt -c <download_url>
6. My download URL :
http://adcdownload.apple.com/Developer_Tools/xcode_3.2.6_and_ios_sdk_4.3__final/xcode_3.2.6_and_ios_sdk_4.3.dmg
7. This file is roughly 4 GB in size !

Installing Google Command Line

2011-10-16T01:07:00.001+05:30

http://code.google.com/p/googlecl/wiki/Install

orable table row count

2011-10-14T13:41:00.001+05:30

SELECT table_name, nvl(num_rows,1)

FROM dba_tables where table_name like 'XYZ';

Mac OS : Forcing black ink printing for Canon MP280 series printer

2011-10-09T18:16:00.001+05:30

System Preferences ->

Printer & Fax ->

Select Canon MP280 on left ->

Options & Supplies ->

Utility ->
Open Printer Utility ->

Ink Cartridge Settings ->

Ink Cartridge : Black Only

Objective C Programming on Windows

2011-10-05T21:49:00.001+05:30

Source

Steps :

1. Download and install these 3 exes : GNUStep 0.23 (System | Core | Devel)
2. Open Programs -> Gnustep -> Shell

3. Create helloworld.m :

 #import <Foundation/Foundation.h>
  int main (int argc, const char * argv[]) { 
  NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];  
 NSLog (@"Hello World!"); 
  [pool drain];  
 return 0;
 }


 4. gcc -o helloworld helloworld.m -I /GNUstep/System/Library/Headers -L /GNUstep/System/Library/Libraries -lobjc -lgnustep-base -fconstant-string-class=NSConstantString

Mac OS quitting front most application

2011-10-05T18:11:00.001+05:30

Command + Q

Mac OS Keyboard shortcut for spotlight

2011-10-05T18:05:00.001+05:30

Command + Space Bar

Mac Window maximize keyboard shortcut

2011-10-04T11:24:00.001+05:30

System Preferences
-> Keyboard & Mouse
-> Keyboard Shortcuts
-> Click the +
-> Make sure it says All Applications in the dropdown.
-> In the menu title type in "Zoom" (Capitalization matters, I believe).
-> Click in the keyboard shortcut area and set the keyboard shortcut
you want. I'd make it a alt-space-x

Useful gmail keyboard shortcuts

2011-10-04T11:22:00.000+05:30

g k -> show task window

Esc -> hide task window

tab Enter -> send mail

Pig RegExp Match

2011-10-03T14:29:00.001+05:30

recs = load 'a.txt';

recs1 = filter recs by $0 matches '.*hiv.*';

dump recs1;

Mac Os : Force ejecting a CD

2011-10-01T00:20:00.001+05:30

On the terminal type :
drutil tray eject

computer programming for kids

2011-09-27T19:33:00.001+05:30

http://www.flipkart.com/books/8184890923

http://www.flipkart.com/books/8177229095

oracle removing all locks

2011-09-27T17:41:00.001+05:30

SELECT l.inst_id,
SUBSTR(L.ORACLE_USERNAME,1,8) ORA_USER,
SUBSTR(L.SESSION_ID,1,3) SID,
S.serial#,
SUBSTR(O.OWNER||'.'||O.OBJECT_NAME,1,40) OBJECT, P.SPID OS_PID,
DECODE(L.LOCKED_MODE, 0,'NONE',
1,'NULL',
2,'ROW SHARE',
3,'ROW EXCLUSIVE',
4,'SHARE',
5,'SHARE ROW EXCLUSIVE',
6,'EXCLUSIVE',
NULL) LOCK_MODE
FROM sys.GV_$LOCKED_OBJECT L
, DBA_OBJECTS O
, sys.GV_$SESSION S
, sys.GV_$PROCESS P
WHERE L.OBJECT_ID = O.OBJECT_ID
and l.inst_id = s.inst_id
AND L.SESSION_ID = S.SID
and s.inst_id = p.inst_id
AND S.PADDR = P.ADDR(+)
order by l.inst_id

alter system kill session '247,52553' immediate;
where 247 is SID and 52553 is serial #

Oracle order tables by creation date

2011-09-16T13:46:00.001+05:30

select * from user_objects where OBJECT_TYPE = 'TABLE' order by created desc;

Oracle explain plan

2011-08-24T19:16:00.000+05:30

1. explain plan set statement_id = 'bad6' for

select a from b;

Then :

2. SELECT cardinality "Rows",

lpad(' ',level-1)||operation||' '||

options||' '||object_name "Plan"

FROM PLAN_TABLE

CONNECT BY prior id = parent_id

AND prior statement_id = statement_id

START WITH id = 0

AND statement_id = 'bad6'

ORDER BY id;

OR

2. SELECT * FROM TABLE(dbms_xplan.display('PLAN_TABLE','bad6','ALL'));

running external script in oracle sqlplus

2011-08-22T12:33:00.001+05:30

SQL> @external.sql

Perl Dollar Dollar ($$)

2011-08-12T15:24:00.000+05:30

Do you know what does $$ stand for in Perl?
It's the process id of the current process.

print $$;

will print the process id of the current process.

Oracle finding indexes/indices for a table

2011-08-04T12:22:00.003+05:30

Select index_name, column_name FROM dba_ind_columns where table_name=’EMP’;

Making the hand tool the default tool on Adobe Reader for Mac OS X

2011-07-29T16:24:00.001+05:30

Source

To set Adobe Reader X to open with the hand tool active what I did was:

Open Adobe Reader X

Right Click on the toolbar

Mouse Down to "Select and Zoom"

Click on the Hand Tool

The Hand Tool appears on the Tool Bar

Click on the Hand Tool

Close Adobe Reader X

The next time you open the Reader the Hand Tool is selected.

PageRank PPT

2011-07-28T12:04:00.003+05:30

PageRank

eigenvector nice explanation

2011-07-28T12:03:00.001+05:30

This is Google's cache of http://www.sosmath.com/matrix/markov/markov.html. It is a snapshot of the page as it appeared on 24 Jul 2011 22:25:14 GMT. The current page could have changed in the meantime. Learn more

Text-only version

These search terms are highlighted: eigenvector stochastic matrix

Markov Chains

In a previous page, we studied the movement between the city and suburbs. Indeed, if I are S are the initial population of the inner city and the suburban area, and if we assume that every year 40% of the inner city population moves to the suburbs, while 30% of the suburb population moves to the inner part of the city, then after one year the populations are given by

The matrix

is very special. Indeed, the entries of each column vectors are positive and their sum is 1. Such vectors are called probability vectors. A matrix for which all the column vectors are probability vectors is called transition orstochastic matrix. Andrei Markov, a russian mathematician, was the first one to study these matrices. At the beginning of this century he developed the fundamentals of the Markov Chain theory.
A Markov chain is a process that consists of a finite number of states and some known probabilities p_ij, where p_ij is the probability of moving from state j to state i. In the example above, we have two states: living in the city and living in the suburbs. The number p_ij represents the probability of moving from state i to state j in one year. We may have more than two states. For example, political affiliation: Democrat, Republican, and Independent. For example, p_ij represents the probability of a son belonging to party i if his father belonged to party j.
Of particular interest is a probability vector p such that , that is, an eigenvector of A associated to the eigenvalue 1. Such vector is called a steady state vector. In the example above, the steady state vectors are given by the system

This system reduces to the equation -0.4 x + 0.3 y = 0. It is easy to see that, if we set , then

So the vector is a steady state vector of the matrix above. So if the populations of the city and the suburbs are given by the vector , after one year the proportions remain the same (though the people may move between the city and the suburbs).

Let us discuss another example on population dynamics.

Example: Age Distribution of Trees in a Forest
Trees in a forest are assumed in this simple model to fall into four age groups: b(k) denotes the number of baby trees in the forest (age group 0-15 years) at a given time period k; similarly y(k),m(k) and o(k) denote the number of young trees (16-30 years of age), middle-aged trees (age 31-45), and old trees (older than 45 years of age), respectively. The length of one time period is 15 years.
How does the age distribution change from one time period to the next? The model makes the following three assumptions:

A certain percentage of trees in each age group dies.
Surviving trees enter into the next age group; old trees remain old.
Lost trees are replaced by baby trees.

Note that the total tree population does not change over time.

We obtain the following difference equations:

b(k+1)	=		(1)
y(k+1)	=	(1-d_b) b(k)	(2)
m(k+1)	=	(1-d_y) y(k)	(3)
o(k+1)	=	(1-d_m) m(k) + (1-d_o) o(k)	(4)

Here 0 < d_b,d_y,d_m,d_o <1 denote the loss rates in each age group in percent.

Let

be the ``age distribution vector". Consider the matrix

Then we have

Note that the matrix A is a stochastic matrix!
If, d_b=.1,d_y=.2,d_m=.3 and d_o=.4, then

After easy calculations, we find the steady state vector for the age distribution in the forest:

Assume a total tree population of 50,000 trees. Suppose the forest is newly planted, i.e.

After 15 years, the age distribution in the forest is given by

After 30 years, we have

and after 45 years

After 15n years, where , the age distribution in the forest is given by

So the problem is to find the n^th-power of the matrix A. We have seen that diagonalization technique may be helpful to solve this problem. Another problem deals with the long term behavior of the sequence x(n) when ngets large.

The calculations on the example above becomes tedious. Let us illustrate the problem on a small matrix.

Example. Consider the stochastic matrix

Note this is a symmetric matrix. The characteristic polynomial of A is

An eigenvector associated to 1 is

and an eigenvector associated to 0.6 is

If we set

then we have

So, we have

When n gets large, the matrices Aⁿ get closer to the matrix

So the sequence of vectors defined by

will get closer to

when n gets large. If , then we have

Note that the vector is proportional to the unique steady state vector of A

This is not surprising. In fact there is a general result similar to the one above for any stochastic matrix.

[Geometry] [Algebra] [Trigonometry ] [Calculus] [Differential Equations] [Matrix Algebra]
S.O.S MATH: Home Page
Do you need more help? Please post your question on our S.O.S. Mathematics CyberBoard.

Author: M.A. Khamsi

Copyright © 1999-2011 MathMedics, LLC. All rights reserved.
Contact us
Math Medics, LLC. - P.O. Box 12395 - El Paso TX 79913 - USA
800 users online during the last hour

pagerank/eigenvector

2011-07-28T12:00:00.002+05:30

Source

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|

How Google Finds Your Needle in the Web's Haystack

As we'll see, the trick is to ask the web itself to rank the importance of pages...

David Austin
Grand Valley State University
david at merganser.math.gvsu.edu

Mail to a friend

Print this article

Imagine a library containing 25 billion documents but with no centralized organization and no librarians. In addition, anyone may add a document at any time without telling anyone. You may feel sure that one of the documents contained in the collection has a piece of information that is vitally important to you, and, being impatient like most of us, you'd like to find it in a matter of seconds. How would you go about doing it?

Posed in this way, the problem seems impossible. Yet this description is not too different from the World Wide Web, a huge, highly-disorganized collection of documents in many different formats. Of course, we're all familiar with search engines (perhaps you found this article using one) so we know that there is a solution. This article will describe Google's PageRank algorithm and how it returns pages from the web's collection of 25 billion documents that match search criteria so well that "google" has become a widely used verb.

Most search engines, including Google, continually run an army of computer programs that retrieve pages from the web, index the words in each document, and store this information in an efficient format. Each time a user asks for a web search using a search phrase, such as "search engine," the search engine determines all the pages on the web that contains the words in the search phrase. (Perhaps additional information such as the distance between the words "search" and "engine" will be noted as well.) Here is the problem: Google now claims to index 25 billion pages. Roughly 95% of the text in web pages is composed from a mere 10,000 words. This means that, for most searches, there will be a huge number of pages containing the words in the search phrase. What is needed is a means of ranking the importance of the pages that fit the search criteria so that the pages can be sorted with the most important pages at the top of the list.

One way to determine the importance of pages is to use a human-generated ranking. For instance, you may have seen pages that consist mainly of a large number of links to other resources in a particular area of interest. Assuming the person maintaining this page is reliable, the pages referenced are likely to be useful. Of course, the list may quickly fall out of date, and the person maintaining the list may miss some important pages, either unintentionally or as a result of an unstated bias.

Google's PageRank algorithm assesses the importance of web pages without human evaluation of the content. In fact, Google feels that the value of its service is largely in its ability to provide unbiased results to search queries; Google claims, "the heart of our software is PageRank." As we'll see, the trick is to ask the web itself to rank the importance of pages.

How to tell who's important

If you've ever created a web page, you've probably included links to other pages that contain valuable, reliable information. By doing so, you are affirming the importance of the pages you link to. Google's PageRank algorithm stages a monthly popularity contest among all pages on the web to decide which pages are most important. The fundamental idea put forth by PageRank's creators, Sergey Brin and Lawrence Page, is this: the importance of a page is judged by the number of pages linking to it as well as their importance.

We will assign to each web page P a measure of its importance I(P), called the page's PageRank. At various sites, you may find anapproximation of a page's PageRank. (For instance, the home page of The American Mathematical Society currently has a PageRank of 8 on a scale of 10. Can you find any pages with a PageRank of 10?) This reported value is only an approximation since Google declines to publish actual PageRanks in an effort to frustrate those would manipulate the rankings.

Here's how the PageRank is determined. Suppose that page P_j has l_j links. If one of those links is to page P_i, then P_j will pass on 1/l_j of its importance to P_i. The importance ranking of P_i is then the sum of all the contributions made by pages linking to it. That is, if we denote the set of pages linking to P_i by B_i, then

This may remind you of the chicken and the egg: to determine the importance of a page, we first need to know the importance of all the pages linking to it. However, we may recast the problem into one that is more mathematically familiar.

Let's first create a matrix, called the hyperlink matrix, in which the entry in the i^th row and j^th column is

Notice that H has some special properties. First, its entries are all nonnegative. Also, the sum of the entries in a column is one unless the page corresponding to that column has no links. Matrices in which all the entries are nonnegative and the sum of the entries in every column is one are called stochastic; they will play an important role in our story.

We will also form a vector whose components are PageRanks--that is, the importance rankings--of all the pages. The condition above defining the PageRank may be expressed as

In other words, the vector I is an eigenvector of the matrix H with eigenvalue 1. We also call this a stationary vector of H.

Let's look at an example. Shown below is a representation of a small collection (eight) of web pages with links represented by arrows.

The corresponding matrix is

with stationary vector

This shows that page 8 wins the popularity contest. Here is the same figure with the web pages shaded in such a way that the pages with higher PageRanks are lighter.

Computing I

There are many ways to find the eigenvectors of a square matrix. However, we are in for a special challenge since the matrix H is a square matrix with one column for each web page indexed by Google. This means that H has about n = 25 billion columns and rows. However, most of the entries in H are zero; in fact, studies show that web pages have an average of about 10 links, meaning that, on average, all but 10 entries in every column are zero. We will choose a method known as the power method for finding the stationary vector I of the matrix H.

How does the power method work? We begin by choosing a vector I⁰ as a candidate for I and then producing a sequence of vectors I^k by

The method is founded on the following general principle that we will soon investigate.

General principle: The sequence I ^k will converge to the stationary vector I.

We will illustrate with the example above.

I ⁰	I ¹	I ²	I ³	I ⁴	...	I ⁶⁰	I ⁶¹
1	0	0	0	0.0278	...	0.06	0.06
0	0.5	0.25	0.1667	0.0833	...	0.0675	0.0675
0	0.5	0	0	0	...	0.03	0.03
0	0	0.5	0.25	0.1667	...	0.0675	0.0675
0	0	0.25	0.1667	0.1111	...	0.0975	0.0975
0	0	0	0.25	0.1806	...	0.2025	0.2025
0	0	0	0.0833	0.0972	...	0.18	0.18
0	0	0	0.0833	0.3333	...	0.295	0.295

It is natural to ask what these numbers mean. Of course, there can be no absolute measure of a page's importance, only relative measures for comparing the importance of two pages through statements such as "Page A is twice as important as Page B." For this reason, we may multiply all the importance rankings by some fixed quantity without affecting the information they tell us. In this way, we will always assume, for reasons to be explained shortly, that the sum of all the popularities is one.

Three important questions

Three questions naturally come to mind:

Does the sequence I^k always converge?
Is the vector to which it converges independent of the initial vector I⁰?
Do the importance rankings contain the information that we want?

Given the current method, the answer to all three questions is "No!" However, we'll see how to modify our method so that we can answer "yes" to all three.

Let's first look at a very simple example. Consider the following small web consisting of two web pages, one of which links to the other:

with matrix

Here is one way in which our algorithm could proceed:

I ⁰	I ¹	I ²	I ³=I
1	0	0	0
0	1	0	0

In this case, the importance rating of both pages is zero, which tells us nothing about the relative importance of these pages. The problem is that P₂ has no links. Consequently, it takes some of the importance from page P₁ in each iterative step but does not pass it on to any other page. This has the effect of draining all the importance from the web. Pages with no links are called dangling nodes, and there are, of course, many of them in the real web we want to study. We'll see how to deal with them in a minute, but first let's consider a new way of thinking about the matrix H and stationary vector I.

A probabilitistic interpretation of H

Imagine that we surf the web at random; that is, when we find ourselves on a web page, we randomly follow one of its links to another page after one second. For instance, if we are on page P_j with l_j links, one of which takes us to page P_i, the probability that we next end up on P_ipage is then .

As we surf randomly, we will denote by the fraction of time that we spend on page P_j. Then the fraction of the time that we end up on pageP_i page coming from P_j is . If we end up on P_i, we must have come from a page linking to it. This means that

where the sum is over all the pages P_j linking to P_i. Notice that this is the same equation defining the PageRank rankings and so . This allows us to interpret a web page's PageRank as the fraction of time that a random surfer spends on that web page. This may make sense if you have ever surfed around for information about a topic you were unfamiliar with: if you follow links for a while, you find yourself coming back to some pages more often than others. Just as "All roads lead to Rome," these are typically more important pages.

Notice that, given this interpretation, it is natural to require that the sum of the entries in the PageRank vector I be one.

Of course, there is a complication in this description: If we surf randomly, at some point we will surely get stuck at a dangling node, a page with no links. To keep going, we will choose the next page at random; that is, we pretend that a dangling node has a link to every other page. This has the effect of modifying the hyperlink matrix H by replacing the column of zeroes corresponding to a dangling node with a column in which each entry is 1/n. We call this new matrix S.

In our previous example, we now have

with matrix

and eigenvector

In other words, page P₂ has twice the importance of page P₁, which may feel about right to you.

The matrix S has the pleasant property that the entries are nonnegative and the sum of the entries in each column is one. In other words, it is stochastic. Stochastic matrices have several properties that will prove useful to us. For instance, stochastic matrices always have stationary vectors.

For later purposes, we will note that S is obtained from H in a simple way. If A is the matrix whose entries are all zero except for the columns corresponding to dangling nodes, in which each entry is 1/n, then S = H + A.

How does the power method work?

In general, the power method is a technique for finding an eigenvector of a square matrix corresponding to the eigenvalue with the largest magnitude. In our case, we are looking for an eigenvector of S corresponding to the eigenvalue 1. Under the best of circumstances, to be described soon, the other eigenvalues of S will have a magnitude smaller than one; that is, if is an eigenvalue of S other than 1.

We will assume that the eigenvalues of S are and that

We will also assume that there is a basis v_j of eigenvectors for S with corresponding eigenvalues . This assumption is not necessarily true, but with it we may more easily illustrate how the power method works. We may write our initial vector I ⁰ as

Then

Since the eigenvalues with have magnitude smaller than one, it follows that if and therefore , an eigenvector corresponding to the eigenvalue 1.

It is important to note here that the rate at which is determined by . When is relatively close to 0, then relatively quickly. For instance, consider the matrix

The eigenvalues of this matrix are and . In the figure below, we see the vectors I ^k, shown in red, converging to the stationary vector I shown in green.

Now consider the matrix

Here the eigenvalues are and . Notice how the vectors I ^k converge more slowly to the stationary vector I in this example in which the second eigenvalue has a larger magnitude.

When things go wrong

In our discussion above, we assumed that the matrix S had the property that and . This does not always happen, however, for the matrices S that we might find.

Suppose that our web looks like this:

In this case, the matrix S is

Then we see

I ⁰	I ¹	I ²	I ³	I ⁴	I ⁵
1	0	0	0	0	1
0	1	0	0	0	0
0	0	1	0	0	0
0	0	0	1	0	0
0	0	0	0	1	0

In this case, the sequence of vectors I ^k fails to converge. Why is this? The second eigenvalue of the matrix S satisfies and so the argument we gave to justify the power method no longer holds.

To guarantee that , we need the matrix S to be primitive. This means that, for some m, S^m has all positive entries. In other words, if we are given two pages, it is possible to get from the first page to the second after following m links. Clearly, our most recent example does not satisfy this property. In a moment, we will see how to modify our matrix S to obtain a primitive, stochastic matrix, which therefore satisfies .

Here's another example showing how our method can fail. Consider the web shown below.

In this case, the matrix S is

with stationary vector

Notice that the PageRanks assigned to the first four web pages are zero. However, this doesn't feel right: each of these pages has links coming to them from other pages. Clearly, somebody likes these pages! Generally speaking, we want the importance rankings of all pages to be positive. The problem with this example is that it contains a smaller web within it, shown in the blue box below.

Links come into this box, but none go out. Just as in the example of the dangling node we discussed above, these pages form an "importance sink" that drains the importance out of the other four pages. This happens when the matrix S is reducible; that is, S can be written in block form as

Indeed, if the matrix S is irreducible, we can guarantee that there is a stationary vector with all positive entries.

A web is called strongly connected if, given any two pages, there is a way to follow links from the first page to the second. Clearly, our most recent example is not strongly connected. However, strongly connected webs provide irreducible matrices S.

To summarize, the matrix S is stochastic, which implies that it has a stationary vector. However, we need S to also be (a) primitive so that and (b) irreducible so that the stationary vector has all positive entries.

A final modification

To find a new matrix that is both primitive and irreducible, we will modify the way our random surfer moves through the web. As it stands now, the movement of our random surfer is determined by S: either he will follow one of the links on his current page or, if at a page with no links, randomly choose any other page to move to. To make our modification, we will first choose a parameter between 0 and 1. Now suppose that our random surfer moves in a slightly different way. With probability , he is guided by S. With probability , he chooses the next page at random.

If we denote by 1 the matrix whose entries are all one, we obtain the Google matrix:

Notice now that G is stochastic as it is a combination of stochastic matrices. Furthermore, all the entries of G are positive, which implies that Gis both primitive and irreducible. Therefore, G has a unique stationary vector I that may be found using the power method.

The role of the parameter is an important one. Notice that if , then G = S. This means that we are working with the original hyperlink structure of the web. However, if , then . In other words, the web we are considering has a link between any two pages and we have lost the original hyperlink structure of the web. Clearly, we would like to take close to 1 so that we hyperlink structure of the web is weighted heavily into the computation.

However, there is another consideration. Remember that the rate of convergence of the power method is governed by the magnitude of the second eigenvalue . For the Google matrix, it has been proven that the magnitude of the second eigenvalue . This means that when is close to 1 the convergence of the power method will be very slow. As a compromise between these two competing interests, Serbey Brin and Larry Page, the creators of PageRank, chose .

Computing I

What we've described so far looks like a good theory, but remember that we need to apply it to matrices where n is about 25 billion! In fact, the power method is especially well-suited to this situation.

Remember that the stochastic matrix S may be written as

and therefore the Google matrix has the form

Therefore,

Now recall that most of the entries in H are zero; on average, only ten entries per column are nonzero. Therefore, evaluating HI ^k requires only ten nonzero terms for each entry in the resulting vector. Also, the rows of A are all identical as are the rows of 1. Therefore, evaluatingAI ^k and 1I ^k amounts to adding the current importance rankings of the dangling nodes or of all web pages. This only needs to be done once.

With the value of chosen to be near 0.85, Brin and Page report that 50 - 100 iterations are required to obtain a sufficiently good approximation to I. The calculation is reported to take a few days to complete.

Of course, the web is continually changing. First, the content of web pages, especially for news organizations, may change frequently. In addition, the underlying hyperlink structure of the web changes as pages are added or removed and links are added or removed. It is rumored that Google recomputes the PageRank vector I roughly every month. Since the PageRank of pages can be observed to fluctuate considerably during this time, it is known to some as the Google Dance. (In 2002, Google held a Google Dance!)

Summary

Brin and Page introduced Google in 1998, a time when the pace at which the web was growing began to outstrip the ability of current search engines to yield useable results. At that time, most search engines had been developed by businesses who were not interested in publishing the details of how their products worked. In developing Google, Brin and Page wanted to "push more development and understanding into the academic realm." That is, they hoped, first of all, to improve the design of search engines by moving it into a more open, academic environment. In addition, they felt that the usage statistics for their search engine would provide an interesting data set for research. It appears that the federal government, which recently tried to gain some of Google's statistics, feels the same way.

There are other algorithms that use the hyperlink structure of the web to rank the importance of web pages. One notable example is the HITS algorithm, produced by Jon Kleinberg, which forms the basis of the Teoma search engine. In fact, it is interesting to compare the results of searches sent to different search engines as a way to understand why some complain of a Googleopoly.

References

Michael Berry, Murray Browne, Understanding Search Engines: Mathematical Modeling and Text Retrieval. Second Edition, SIAM, Philadelphia. 2005.
Sergey Brin, Lawrence Page, The antaomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems,33: 107-17, 1998. Also available online at http://infolab.stanford.edu/pub/papers/google.pdf
Kurt Bryan, Tanya Leise, The $25,000,000,000 eigenvector. The linear algebra behind Google. SIAM Review, 48 (3), 569-81. 2006. Also avaiable at http://www.rose-hulman.edu/~bryan/google.html
Google Corporate Information: Technology.
Taher Haveliwala, Sepandar Kamvar, The second eigenvalue of the Google matrix.
Amy Langville, Carl Meyer, Google's PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, 2006.
This is an informative, accessible book, written in an engaging style. Besides providing the relevant mathematical background and details of PageRank and its implementation (as well as Kleinberg's HITS algorithm), this book contains many interesting "Asides" that give trivia illuminating the context of search engine design.

David Austin
Grand Valley State University
david at merganser.math.gvsu.edu

NOTE: Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Some of the items above can be accessed via the ACM Portal, which also provides bibliographic services.

Comments: Email Webmaster	© Copyright 2011, American Mathematical Society Contact Us · Sitemap · Privacy Statement	Powered by Translate

Oracle show create table

2011-07-26T14:43:00.001+05:30

select dbms_metadata.get_ddl('TABLE','table_name','db_name') from dual;
select dbms_metadata.get_ddl('INDEX','index_name','db_name') from dual;

Oracle show indexes/indices

2011-07-26T14:42:00.000+05:30

select index_name from dba_indexes where table_name='tablename';

pig : set default parallelism at the script level

2011-06-24T17:01:00.001+05:30

SET default_parallel 100; -- make it the first line in the script

Everything you wanted to know about Pig

2011-06-21T16:45:00.008+05:30

http://wiki.apache.org/pig/PigLatin

http://pig.apache.org/docs/r0.7.0/piglatin_ref1.html

http://wiki.apache.org/pig/PigStreamingFunctionalSpec

http://search.safaribooksonline.com/book/databases/hadoop/9780596521974/pig/301

http://pig.apache.org/docs/r0.7.0/piglatin_ref2.html#CONCAT

http://ofps.oreilly.com/titles/9781449302641/index.html

Mysql to Pig converter

mysql to pig converter

2011-06-17T14:54:00.001+05:30

Source

Oracle previous command

2011-06-14T16:06:00.003+05:30

SQL> edit
----
edit the command
-----
/

Oracle show tables

2011-06-14T16:06:00.001+05:30

select * from user_objects where object_type = 'TABLE';

Removing certificate exceptions in firefox

2011-06-02T15:30:00.001+05:30

Source

Stopping/halting search(and other long processes) in vim

2011-05-23T16:12:00.001+05:30

Ctrl-C

wget on mac

2011-05-23T15:28:00.001+05:30

use :
curl -O url

Java static class

2011-05-17T14:56:00.001+05:30

http://stackoverflow.com/questions/70324/java-inner-class-and-static-nested-class
http://stackoverflow.com/questions/1353309/java-static-vs-non-static-inner-class
http://download.oracle.com/javase/tutorial/java/javaOO/nested.html
http://stackoverflow.com/questions/3584113/java-static-class

hadoop combiner class

2011-05-17T14:55:00.001+05:30

http://wiki.apache.org/hadoop/HadoopMapReduce

http://singaraju.com/blogs/gautam/2010/02/25/hadoop-effectiveness-of-a-combiner-class/

MapReduce for dummies

2011-05-16T11:46:00.001+05:30

http://www.joelonsoftware.com/items/2006/08/01.html

Mac Firefox Hard refresh

2011-05-13T13:56:00.000+05:30

Command + Shift + R

Normal refresh : Command + R

Source

a useful firefox seo plugin

2011-05-12T17:34:00.000+05:30

seoquake

a useful firefox seo plugin

2011-05-12T15:49:00.000+05:30

www.seoquake.com/

popular seo blogs

2011-05-10T14:57:00.003+05:30

Matt Cutts
Matt's blog site is not just about SEO. Matt shares his thoughts on many other
things, including food, personal information, and Google's Chrome web browser.
Nonetheless, the site does contain more than 400 posts related to SEO—enough
to keep you reading for a few days!

Search Engine Land
This blog provides news and information about SEM, SEO, and how search engines
work.

SEOBook
This is one of the most popular SEO sites, providing online (free and paid) training
and information.

Graywolf's SEO Blog
This is an informative, thought-provoking SEO blog.

SEO by the Sea
This blog provides marketing and SEO information and services.

SEOmoz
Boasting more than 60,000 members, this blog provides free and paid SEO information and services.

Search Engine Watch
The Search Engine Watch blog offers tips on SEM and SEO and the latest news
about search engines.

SEO Chat
This blog provides information on SEO and other search engine–related news.

Search Engine Roundtable
This blog provides the latest information on SEO, SEM, and search engines.

Search Engine Journal
This blog provides the latest search engine news, including SEO news.

Source

adwords experiments you can try

2011-05-10T14:48:00.001+05:30

negative keywords
A/B testing
multivariate testing

on analytics
try funnels

for reverse ip lookup

2011-05-10T13:52:00.001+05:30

www.yougetsignal.com

back link checkers

2011-05-10T13:33:00.001+05:30

Link Diagnosis
(http://www.linkdiagnosis.com/) Provides an online backlink report; allows CSV export

Backlink Watch
(http://www.backlinkwatch.com/) Provides an online backlink report with several additional features including outbound link counts

Backlink Checker
(http://www.iwebtool.com/) Provides basic backlink checker functionality with associated Google PageRank
values

source

Useful google search operators

2011-05-10T13:28:00.001+05:30

inurl: www. competitorURL.com
inanchor: www. competitorURL.com
intitle: www. competitorURL.com
allintitle: www. competitorURL.com
allintitle: www. competitorURL.com site:.org
site: . edu inanchor:www.competitorURL.com
site: . gov inanchor:www.competitorURL.com

Source

OAuth for dummies

2011-05-09T14:58:00.001+05:30

A real good explanation of OAuth.

Installing ruby on RHEL

2011-05-09T13:33:00.002+05:30

wget ftp://ftp.ruby-lang.org/pub/ruby/1.9/ruby-1.9.0-0.tar.gz
tar -xvzf ruby-1.9.0-0.tar.gz
cd ruby-1.9.0-0
./configure
make
sudo make install

SEO firefox plugin

2011-05-05T14:04:00.001+05:30

SEOQuake

SEO directories

2011-05-04T18:49:00.001+05:30

all of the first-tier directories, including
Dmoz.org, Yahoo! Directory, Business.com, and YellowPages.com.

searching directories :
directory "submit a link"
general directories
directory of directories
"general directory"
site: dmoz. org inurl:directories
small business "add url"|"add link"
+general +directory add url|link free|paid

searching directories :
travel site: dmoz.org inurl:directories
"insurance broker directory"
wine producers directory
electronics manufacturer directory
jewelry stores directory

regional directories :
toronto "travel agencies" +directory
ontario "travel agencies" directory
canada "travel agencies" directory
boston "pizza restaurants" directory
new york "shoe stores" directory
los angeles inurl:directory
You can visit http://www.isedb.com/html/Web_Directories/ to find more regional directory listings. You can find another directory repository at http://www.web-directories
.ws/Regional/.

Article submission :
Many sites let you submit your articles, including ArticlesBase, EzineArticles, Article
Geek, and many others. When you choose your article submission vendor, ensure that
your articles are always properly credited.

Taking a screenshot on Mac

2011-05-04T15:21:00.001+05:30

Press Command + Shift + 3 and click your mouse anywhere on the screen after that.
The screenshot will be saved on the Desktop.

google.com/ncr

2011-05-01T01:21:00.001+05:30

to avoid country redirect.

SEO meta tags

2011-04-19T15:35:00.003+05:30

Source

Search engines will sometimes opt to ignore them in favor of the
description used at Dmoz.org or in the Yahoo! Directory
(if you have a listing there).

To help webmasters control this scenario, new meta tag variations were
created to force
search engines to use the <meta> description tag instead of the
description found in the
directory listings. Here are examples that detail ways to block either
Dmoz.org or Yahoo! Directory descriptions:

<! -- Tells Yahoo! to not use Yahoo! Directory description -->
<meta name="robots" content="noydir" />

<! -- Tells search engines to not use ODP description -->
<meta name="robots" content="noodp" />

<! -- Tells search engines to not use either of the two directories -->
<meta name="robots" content="noodp,noydir" />

If you wish to target only specific spiders, you can do the following:
<meta name="googlebot" content="noodp">
<! -- Note: Only Yahoo! uses Yahoo! Directory -->

<meta name="slurp" CONTENT="noydir">
<meta name="msnbot" CONTENT="noodp">

SEO lessons

2011-04-19T10:56:00.001+05:30

1. The title of your page should contain keywords which can actually be
found in the page's content.

2. Make the meta tag description human readable.

Domain name suggestion tools

2011-04-15T16:41:00.000+05:30

Source

DomainsBot (http://www.domainsbot.com)
Provides advanced (semantic) domain name lookup tools

DomainTools (http://www.domaintools.com)
Allows you to enter an existing domain name or a phrase and
then shows you a list of 20 domain name suggestions and their
availability for .com, .net, .org, .info, .biz, and .us extensions

BUST A NAME (http://www.bustaname.com)
Lets you add words in one pane, and then produces
combinations of domain name suggestions

Nameboy (http://nameboy.com)
Allows for hyphen and rhyme options

MakeWords(http://makewords.com)
Generates multilingual domain names

Nonsense word generators :
Word Generator
(http://www.kessels.com/WordGenerator/) Generates 50 words on each page refresh
Web 2.0 Domain Name Generator
(http://www.hackslash.net/?page_id=48) Generates 15 words after you click the Submit button
SoyBomb
(http://www.soybomb.com/tricks/words/) Generates 50 words on each page refresh

How to start firefox in private mode by default

2011-04-14T11:12:00.001+05:30

In about:config set browser.privatebrowsing.autostart to true.

Macbook pro going to beginning/end of commad line on Terminal

2011-03-30T12:19:00.002+05:30

Ctrl-A for beginning
Ctrl-E for end

Mac terminal does not load .bashrc

2011-03-30T11:21:00.001+05:30

It loads .bash_profile.
So put your aliases there.

Sorting IP addresses

2011-01-28T15:40:00.001+05:30

Where input_file contains one IP address per line.

sort -u -t . -k 1,1n -k 2,2n -k 3,3n -k 4,4n input_file

Wikimedia : preventing new account creation

2011-01-28T13:31:00.001+05:30

In LocalSettings.php, add this :

# Prevent new user registrations except by sysops
$wgGroupPermissions['*']['createaccount'] = false;

Source

wikimedia prevent access

2011-01-27T23:40:00.000+05:30

Source

Exercises to stop snoring

2011-01-25T14:09:00.001+05:30

- Repeat each vowel (a,e,i,o,u) out loud for three minutes throughout day.
- Place the tip of your tongue behind your top front teeth. Slide your tongue backwards for 3 minutes a day.
- Close your mouth and purse your lips. Hold for 30 seconds.
- With mouth open, move jaw to the right and hold for 30 seconds. Repeat on left side.

Source

Mac switching between windows like windows alt-tab

2011-01-18T23:13:00.001+05:30

For switching between applications : Command+Tab
For switching between windows of a single application : Command + ~(tilda)

SVN Status Simple Cheat Sheet

2011-01-17T15:38:00.001+05:30

Source

SVN Status Simple Cheat Sheet

svn adding/deleting new/missing files from command line

2011-01-17T13:11:00.002+05:30

Source

Deleting missing files :
svn st | grep ^! | awk '{print $2}' | xargs svn delete

Adding new files
svn st | grep ^? | awk '{print $2}' | xargs svn add

Permission denied on MAC

2011-01-14T20:40:00.001+05:30

sudo chown -R $(id -u):$(id -g) MyDirectory
chmod -R u+w MyDirectory

Source

svn on hostmonster

2011-01-12T22:46:00.001+05:30

Source
wget http://subversion.tigris.org/downloads/subversion-1.4.6.tar.bz2
wget http://subversion.tigris.org/downloads/subversion-deps-1.4.6.tar.bz2
tar xjf subversion-1.4.6.tar.bz2
tar xjf subversion-deps-1.4.6.tar.bz2
mkdir svn
cd subversion-1.4.6
./configure --prefix=$HOME/svn --with-expat=builtin --with-pic --with-ssl
make
make install
vim ~/.bashrc (add svn/bin to the path)

Making terminal vim the default text editor on Mac

2011-01-12T20:45:00.000+05:30

Making terminal vim the default text editor on Mac

Firefox : Mac : keyboard shortcut for going to address bar

2011-01-12T20:24:00.001+05:30

Command + L - source

Firefox : Mac : keyboard shortcut for going to address bar

2011-01-12T20:23:00.000+05:30

Command + L - source

Mac book pro : Page up/down

2011-01-12T20:22:00.001+05:30

While holding down the fn key, use the up and down arrows to achieve page up and page down. - source

Mac book pro : Page up/down

2011-01-12T20:19:00.000+05:30

While holding down the fn key, use the up and down arrows to achieve page up and page down. - source

Mysql Create new user

2011-01-09T19:23:00.001+05:30

CREATE USER 'monty'@'localhost' IDENTIFIED BY 'some_pass';
mysql> GRANT ALL PRIVILEGES ON *.* TO 'monty'@'localhost'
-> WITH GRANT OPTION;
mysql> CREATE USER 'monty'@'%' IDENTIFIED BY 'some_pass';
mysql> GRANT ALL PRIVILEGES ON *.* TO 'monty'@'%'
-> WITH GRANT OPTION;
mysql> CREATE USER 'admin'@'localhost';
mysql> GRANT RELOAD,PROCESS ON *.* TO 'admin'@'localhost';
mysql> CREATE USER 'dummy'@'localhost';

Google's AROUND Operator for Proximity Search

2010-12-22T18:30:00.002+05:30

Google's AROUND Operator for Proximity Search

via Google Operating System by Alex Chitu on 12/8/10

Google has an undocumented operator called "AROUND" for finding web pages that include words or phrases which are near to each other.

If you want to find results that include both "Steve Jobs" and "Andy Rubin", you might search for ["Steve Jobs" "Andy Rubin"] or even for ["Steve Jobs * Andy Rubin"]. Google's AROUND operator lets you specify the maximum number of words that separate the two names. For example, you could search for ["Steve Jobs" AROUND(3) "Andy Rubin"] and only get web pages that include the two names separated by less than three words.

"The AROUND operator is a handy trick to use when you're looking for a combination of search terms when one dominates the results, but you're interested in the relationship between two query terms. Note also that if Google can't find anything within the limit, it will just do regular ranking of the terms without the AROUND coming into play. Using AROUND is especially useful when the documents are rather long (think book-length articles). So try this operator in Google Books.... [slavery AROUND(4) indigo]," suggests Google's Daniel Russell.

Barry Schwartz notes that Bing has a similar operator, but it's called "near".

{ via Search Engine Roundtable }

Joining all lines in a file with comma

2010-12-21T17:41:00.001+05:30

awk '{ printf "%s," ,$0 }' file.txt > newfile.txt

Mysql db count tables

2010-12-20T12:24:00.001+05:30

select count(*) as number_of_tables
from information_schema.tables
where table_schema = 'my favourite schema'

linux : extracting a line range from a file

2010-12-17T16:21:00.001+05:30

sed -n 2,4p somefile.txt

mediawiki useful tables - pass 1

2010-12-13T14:23:00.001+05:30

user
searchindex
logging

Find the minimum difference between two arrays

2010-12-11T00:43:00.001+05:30

Given two sorted arrays, A and B, find i,j for which |A[i] - B[j]| is minimum

Longest sequence of d-dimensional boxes fitting into each other

2010-12-11T00:42:00.001+05:30

Interview question :
You have 'n' d-dimensional boxes.
You have to find out the longest sequence
of boxes which fit into each other.

Hints :
1. How do you say that whether a 3-d box
fits into another?
2. Extend it to d-dimensions.
3. It's possible to do a bfs on a directed-acyclic-graph
without keeping a 'visited' lookup table, since it will
never go in an infinite loop.
4. Finding longest path in a graph is NP-complete.

Encoding/decoding a tree

2010-12-11T00:41:00.005+05:30

How do you encode a tree, send it over
the wire and decode it.
Give algorithms for encoding/decoding.

Location of an element where index is same as the value

2010-12-11T00:41:00.003+05:30

In a sorted integer array,

find an index, for which the
value is same as the index, i.e. a[i] is same as i.

For e.g. in a = {-2,0,2,3}
a[2] is 2, so the answer is 2.

In {1,2,5,7}, there is no such index.

My answer is on the lines of binary-search,
but would also like to see other answers.

Locker design interview question

2010-12-11T00:41:00.001+05:30

You have to design a locker system where people
can deposit their bags of 3 types : small,medium,big.
And there are 3 types of lockers : small,medium,big.
Let's say there are 'n' lockers of each type.

Also, a small bag goes in a small locker,
a big bag in the big locker and so on.

You need to support two operations.
1. deposit a bag
2. retrieve a bag(when the depositor comes back)

interview questions

2010-12-11T00:15:00.001+05:30

find the height of a binary tree, iteratively

Interview question

2010-12-07T20:35:00.001+05:30

I have 6 million co-ordinates of the type (x,y).
I know the bounding rectangle for those points,
that is I know the min(x),min(y),max(x),max(y)
on the complete range.

Now, write a function closestTen(x,y), which
will take a (x,y) point as input and find its 10 closest
neighbors in the given bounding rectangle.

This input (x,y) can be inside the bounding rectangle
or outside it. It may also be one of the 6 million points,
but not necessarily.

Some Interview questions

2010-12-07T13:55:00.001+05:30

1. Given a sorted array which has distinct integers in ascending order,
find an index where a[k] = k;
Solution : modified binary search

2. Give me the data structure and algorithm for a locker system
where there are 3 types of lockers big,medium and small. Number of
lockers is n for every type.
Customers come with 3 types of bags, big,medium and small.
Small bag goes in small locker, and so on...

You have to support two operations :
a. insert bag,
b. retrieve bag.

For both of the operations, the expected time complexity is O(1).

3. Given a binary search tree, find two elements which sum up to k.
Solution : convert it into a doubly linked list and then solve the problem
as if you are solving it for an array.

php echo print difference

2010-12-06T12:32:00.001+05:30

echo is faster, since it doesn't return anything as opposed
to print

PHP how to get the browser information

2010-12-06T12:31:00.001+05:30

through $_SERVER[], a parameter called HTTP_USER_AGENT,
may be coupled with get_browser method.

GET POST difference

2010-12-06T12:30:00.001+05:30

1. POST is superset of get, that is it reads data from querystring as
well as the request body,
whereas GET reads data only from the queryString.
2. Results of GET can be cached, not POST.
3. Sending passwords by GET can expose your password to :
(a) a casual observer looking over your shoulder
(b) someone reading server logs
(c) in referrer information
4. Through POST, you can send more data.
5. resubmitting a POST request prompts(should prompt) user.
6. GET or query string posts are really good for information required
for either bookmarking a particular item, or for assisting in search
engine optimization and indexing items.

BST in PHP

2010-12-04T21:26:00.001+05:30

Web Security issues

2010-12-04T00:17:00.001+05:30

1. Cross Site Request Forgery : (CSRF)

Types
A.
Change the DNS entry for the server in the ADSL of the user for a particular domain,
so that the request goes to a different domain altogether

B.
For e.g. a URL in one of the forums which Bob uses :
<img src="http://bank.example.com/withdraw?account=bob&amount=1000000&for=mallory">
If Bob's cookies haven't expired, this will benefit mallory.

Prevention :
1. Add authentication token in GET/POST
2. Check referrer
3. secret token
4. crossdomain.xml

2. Replay attack :
Evasdrop on a client server communication and re-play it.
Prevention :
Server should the client a one-time use token.
Other Issues :

3. Cross site cooking / Cross sub domain cooking (allowing a web site to set cookies for other domains/sub domains)
then, if the affected person logs on, evil person can use that cookie
General solutions :
generate new SId, before something crucial.
destroy session for malicious referrer
check browser etc information
time out old SIDs.

4. A billion laughs :

<!DOCTYPE root [
<!ENTITY ha "Ha! ">
<!ENTITY ha2 "&ha;&ha;">
<!ENTITY ha3 "&ha2;&ha2;">
<!ENTITY ha4 "&ha3;&ha3;">
<!ENTITY ha5 "&ha4;&ha4;">
...
<!ENTITY ha128 "&ha127;&ha127;">
]>
<root>&ha128;</root>

5. Similar to a Billion laughs :

ReDos (Regular expression Denial of Service)

Cross site scripting attack (Google example)

2010-12-04T00:15:00.000+05:30

Source

The script (http://www.google.com/url?q=...) is normally used for redirecting the browser from Google's website to other sites.

For example, the following request will redirect the browser to http://www.watchfire.com:
http://www.google.com/url?q=http://www.watchfire.com

When the parameter (q) is passed to the script with illegal format (The format seems to be: http://domain), a "403 Forbidden" page returns to the user, informing that the query was illegal. The parameter's value appears in the HTML returned to the user.

If http://www.google.com/url?q=USER_INPUT is requested, the text in the "403 Forbidden" response would be:
"Your client does not have permission to get URL /url?q=USER_INPUT from this server."

The server response lacks charset encoding enforcement, such as:
* Response headers: "Content-Type: text/html; charset=[encoding]".
* Response body: "<meta http-equiv="Content-Type" (...) charset=[encoding]/>".

Google's 404 NOT FOUND mechanism:
When requesting a page which doesn't exist under www.google.com, a 404 NOT FOUND response is returned to the user, with the original path requested.

If http://www.google.com/NOTFOUND is requested, the following text appears in the response:
"Not Found The requested URL /NOTFOUND was not found on this server."

The server response lacks charset encoding enforcement, such as:
* Response headers: "Content-Type: text/html; charset=[encoding]".
* Response body: "<meta http-equiv="Content-Type" (...) charset=[encoding]/>".

XSS vulnerabilities:
While the aforementioned mechanisms (URL redirection script, 404 NOT FOUND) escape common characters used for XSS, such as <> (triangular parenthesis) and apostrophes, it fails to handle hazardous UTF-7 encoded payloads.

Therefore, when sending an XSS attack payload, encoded in UTF-7, the payload will return in the response without being altered.

For the attack to succeed (script execution), the victims browser should treat the XSS payload as UTF-7.

IE charset encoding Auto-Selection:
If 'Encoding' is set to 'Auto-Select', and Internet-Explorer finds a UTF-7 string in the first 4096 characters of the response's body, it will set the charset encoding to UTF-7 automatically, unless a certain charset encoding is already enforced.

This automatic encoding selection feature makes it possible to mount UTF-7 XSS attacks on Google.com.

Solution:
Google solved the aforementioned issues at 01/12/2005, by using character encoding enforcement.

Some db performance optimizations

2010-12-03T23:56:00.001+05:30

1. Materialized views :

Views where the results are cached, and updated time-to-time.

2. Save the result of aggregate operations, and refresh periodically ( or use triggers)

(for e.g. stackoverflow updates your accept rate, not immediately, but after some time)

3. Vertically split tables (by columns), keep the primary key column in both the partitions.

If the original table is being maintained, no need to carry over the RI constraints.

4. Redundant data

table1(empid,empname,deptId) table2(deptId,deptName)

if empname,deptName are usually fetched together, ponder

copying the deptName to the first table.

5. While dealing with repeating groups, you can consider having multiple columns

rather than multiple rows in order fasten the access.

but before doing this know that,

-> it will be difficult to aggregate the data

-> it will be accessed collectively

Data Denormalization guidelines

2010-12-03T23:52:00.001+05:30

this page mirrored from the The Data Adminstration Newsletter www.tdan.com. Please visit them for more.

DENORMALIZATION GUIDELINES
Craig S. Mullins, PLATINUM technology, inc.

Normalization is the process of putting one fact in one appropriate place. This optimizes updates at the expense of retrievals. When a fact is stored in only one place, retrieving many different but related facts usually requires going to many different places. This tends to slow the retrieval process. Updating is quicker, however, because the fact you're updating exists in only one place.

It is generally recognized that all relational database designs should be based on a normalized logical data model. With a normalized data model, one fact is stored in one place, related facts about a single entity are stored together, and every column of each entity refers non-transitively to only the unique identifier for that entity. Although an in-depth discussion of normalization is beyond the scope of this article, brief definitions of the first three normal forms follow:

In first normal form, all entities must have a unique identifier, or key, that can be composed of one or more attributes. In addition, all attributes must be atomic and non-repeating. (Atomic means that the attribute must not be composed of multiple attributes. For example, EMPNO should not be composed of social security number and last name because these are separate attributes.)
In second normal form, all attributes that are not part of the key must depend on the entire key for that entity.
In third normal form, all attributes that are not part of the key must not depend on any other non-key attributes.

Frequently, however, performance needs dictate very quick retrieval capability for data stored in relational databases. To accomplish this, sometimes the decision is made to denormalize the physical implementation. Denormalization is the process of putting one fact in numerous places. This speeds data retrieval at the expense of data modification.

It is not the intention of this article to promote the concept of denormalization. Of course, a normalized set of relational tables is the optimal environment and should be implemented for whenever possible. Yet, in the real world, denormalization is sometimes necessary. Denormalization is not necessarily a bad decision if implemented wisely. You should always consider these issues before denormalizing:

can the system achieve acceptable performance without denormalizing?
will the performance of the system after denormalizing still be unacceptable?
will the system be less reliable due to denormalization?

If the answer to any of these questions is "yes," then you should avoid denormalization because any benefit that is accrued will not exceed the cost. If, after considering these issues, you decide to denormalize be sure to adhere to the general guidelines that follow.

If enough DASD is available at your shop, create two sets of tables: one set fully normalized and another denormalized. Populate the denormalized versions by querying the data in the normalized tables and loading or inserting it into the denormalized tables. Your application can access the denormalized tables in a read-only fashion and achieve performance gains. It is imperative that a controlled and scheduled population function is maintained to keep the data in the denormalized and normalized tables synchronized.

If DASD is not available for two sets of tables, then maintain the denormalized tables programmatically. Be sure to update each denormalized table representing the same entity at the same time, or alternately, to provide a rigorous schedule whereby tables will be synchronized. At any rate, all users should be informed of the implications of inconsistent data if it is deemed impossible to avoid unsynchronized data.

When updating any column that is replicated in many different tables, always update it everywhere that it exists simultaneously, or as close to simultaneously as possible given the physical constraints of your environment. If the denormalized tables are ever out of sync with the normalized tables be sure to inform end-users that batch reports and on-line queries may not contain sound data; if at all possible, this should be avoided.

Finally, be sure to design the application so that it can be easily converted from using denormalized tables to using normalized tables.

The Reason for Denormalization

Only one valid reason exists for denormalizing a relational design - to enhance performance. However, there are several indicators which will help to identify systems and tables which are potential denormalization candidates. These are:

Many critical queries and reports exist which rely upon data from more than one table. Often times these requests need to be processed in an on-line environment.
Repeating groups exist which need to be processed in a group instead of individually.
Many calculations need to be applied to one or many columns before queries can be successfully answered.
Tables need to be accessed in different ways by different users during the same timeframe.
Many large primary keys exist which are clumsy to query and consume a large amount of DASD when carried as foreign key columns in related tables.
Certain columns are queried a large percentage of the time. Consider 60% or greater to be a cautionary number flagging denormalization as an option.

Be aware that each new RDBMS release usually brings enhanced performance and improved access options that may reduce the need for denormalization. However, most of the popular RDBMS products on occasion will require denormalized data structures. There are many different types of denormalized tables which can resolve the performance problems caused when accessing fully normalized data. The following topics will detail the different types and give advice on when to implement each of the denormalization types.

Pre-Joined Tables

If two or more tables need to be joined on a regular basis by an application, but the cost of the join is prohibitive, consider creating tables of pre-joined data. The pre-joined tables should:

contain no redundant columns (matching join criteria columns)
contain only those columns absolutely necessary for the application to meet its processing needs
be created periodically using SQL to join the normalized tables

The cost of the join will be incurred only once when the pre-joined tables are created. A pre-joined table can be queried very efficiently because every new query does not incur the overhead of the table join process.

Report Tables

Often times it is impossible to develop an end-user report using SQL or QMF alone. These types of reports require special formatting or data manipulation. If certain critical or highly visible reports of this nature are required to be viewed in an on-line environment, consider creating a table that represents the report. This table can then be queried using SQL, QMF, and/or another report facility. The report should be created using the appropriate mechanism (application program, 4GL, SQL, etc.) in a batch environment. It can then loaded into the report table in sequence. The report table should:

contain one column for every column of the report
have a clustering index on the columns that provide the reporting sequence
not subvert relational tenets (such as, 1NF and atomic data elements)

Report tables are ideal for carrying the results of outer joins or other complex SQL statements. If an outer join is executed and then loaded into a table, a simple SELECT statement can be used to retrieve the results of the outer join, instead of the complex UNION technique shown in Figure 1. Some RDBMS products support an explicit outer join function which can be used instead of the UNION depicted. However, depending on the implementation, the explicit outer join may be simpler or more complex than the UNION it replaces.

Figure 1. Outer Join Technique Using UNION

Mirror Tables

If an application system is very active it may be necessary to split processing into two (or more) distinct components. This requires the creation of duplicate, or mirror tables. Consider an application system that has very heavy on-line traffic during the morning and early afternoon hours. This traffic consists of both querying and updating of data. Decision support processing is also performed on the same application tables during the afternoon. The production work in the afternoon always seems to disrupt the decision support processing causing frequent time outs and dead locks.

This situation could be corrected by creating mirror tables. A foreground set of tables would exist for the production traffic and a background set of tables would exist for the decision support reporting. A mechanism to periodically migrate the foreground data to background tables must be established to keep the application data synchronized. One such mechanism could be a batch job executing UNLOAD and LOAD utilities. This should be done as often as necessary to sustain the effectiveness of the decision support processing.

It is important to note that since the access needs of decision support are often considerably different than the access needs of the production environment, different data definition decisions such as indexing and clustering may be chosen for the mirror tables.

Split Tables

If separate pieces of one normalized table are accessed by different and distinct groups of users or applications then consider splitting the table into two (or more) denormalized tables; one for each distinct processing group. The original table can also be maintained if other applications exist that access the entire table. In this scenario the split tables should be handled as a special case of mirror table. If an additional table is not desired then a view joining the tables could be provided instead.

Tables can be split in one of two ways: vertically or horizontally. Refer to Figure 2. A vertical split cuts a table column-wise, such that one group of columns is placed into one new table and the remaining columns are placed in another new table. A horizontally split table is a row-wise split. To split a table horizontally, rows are classified into groups via key ranges. The rows from one key range are placed in one table, those from another key range are placed in a different table, and so on.

Vertically split tables should be created by placing the primary key columns for the old, normalized table into both of the split tables. Designate one of the two, new tables as the parent table for the purposes of referential integrity unless the original table still exists. In this case, the original table should be the parent table in all referential constraints. If this is the case, and the split tables are read only, do not set up referential integrity (RI) for the split tables as they are being derived from a referentially intact source. RI would be redundant.

When a vertical split is being done, always include one row per primary key in each split table. Do not eliminate rows from either of the two tables for any reason. If rows are eliminated the update process and any retrieval process that must access data from both tables will be unnecessarily complicated.

When a horizontal split is being done, try to split the rows between the new tables to avoid duplicating any one row in each new table. This is done by splitting using the primary key such that discrete key ranges are placed in separate split tables. Simply stated, the operation of UNION ALL, when applied to the horizontally split tables, should not add more rows than contained in the original, un-split tables. Likewise, it should not contain fewer rows either.

Combined Tables

If tables exist with a one-to-one relationship consider combining them into a single combined table. Sometimes, even one-to-many relationships can be combined into a single table, but the data update process will be significantly complicated because of the increase in redundant data.

For example, consider an application with two tables: DEPT (containing department data) and EMP (containing employee data). Combining the two tables into a large table named, for example, EMP_WITH_DEPT. This new table would contain all of the columns of both tables except for the redundant DEPTNO column (the join criteria). So, in addition to all of the employee information, all of the department information would also be contained on each employee row. This will result in many duplicate instances of the department data. Combined tables of this sort should be considered pre-joined tables and treated accordingly. Tables with one to one relationships should always be analyzed to determine if combination is useful.

Redundant Data

Sometimes one or more columns from one table are accessed whenever data from another table is accessed. If these columns are accessed frequently with tables other than those in which they were initially defined, consider carrying them in those other tables as redundant data. By carrying these additional columns, joins can be eliminated and the speed of data retrieval will be enhanced. This should only be attempted if the normal access is debilitating.

Consider, once again, the DEPT and EMP tables. If most of the employee queries require the name of the employee's department then the department name column could be carried as redundant data in the EMP table. The column should not be removed from the DEPT table, though (causing additional update requirements if the department name changes).

In all cases columns that can potentially be carried as redundant data should be characterized by the following attributes:

only a few columns are necessary to support the redundancy
the columns should be stable, being updated only infrequently
the columns should be used by either a large number of users or a few very important users

Repeating Groups

When repeating groups are normalized they are implemented as distinct rows instead of distinct columns. This usually results in higher DASD usage and less efficient retrieval because there are more rows in the table and more rows need to be read in order to satisfy queries that access the repeating group.

Sometimes, denormalizing the data by storing it in distinct columns can achieve significant performance gains. However, these gains come at the expense of flexibility. For example, consider an application that is storing repeating group information in the normalized table below:

This table can store an infinite number of balances per customer, limited only by available storage and the storage limits of the RDBMS. If the decision were made to string the repeating group, BALANCE, out into columns instead of rows, a limit would need to be set for the number of balances to be carried in each row. An example of this after denormalization is shown below:

In this example, only six balances may be stored for any one customer. The number six is not important, but the concept that the number of values is limited is important. This reduces the flexibility of data storage and should be avoided unless performance needs dictate otherwise.

Before deciding to implement repeating groups as columns instead of rows be sure that the following criteria are met:

the data is rarely or never aggregated, averaged, or compared within the row
the data occurs in a statistically well-behaved pattern
the data has a stable number of occurrences
the data is usually accessed collectively
the data has a predictable pattern of insertion and deletion

If any of the above criteria are not met, SQL SELECT statements may be difficult to code making the data less available due to inherently unsound data modeling practices. This should be avoided because, in general, data is denormalized only to make it more readily available.

Derivable Data

If the cost of deriving data using complicated formulae is prohibitive then consider storing the derived data in a column instead of calculating it. However, when the underlying values that comprise the calculated value change, it is imperative that the stored derived data also be changed otherwise inconsistent information could be reported. This will adversely impact the effectiveness and reliability of the database.

Sometimes it is not possible to immediately update derived data elements when the columns upon which they rely change. This can occur when the tables containing the derived elements are off-line or being operated upon by a utility. In this situation, time the update of the derived data such that it occurs immediately when the table is made available for update. Under no circumstances should outdated derived data be made available for reporting and inquiry purposes.

Hierarchies

A hierarchy is a structure that is easy to support using a relational database such as DB2, but is difficult to retrieve information from efficiently. For this reason, applications which rely upon hierarchies very often contain denormalized tables to speed data retrieval. Two examples of these types of systems are the classic Bill of Materials application and a Departmental Reporting system. A Bill of Materials application typically records information about parts assemblies in which one part is composed of other parts. A Department Reporting system typically records the departmental structure of an organization indicating which departments report to which other departments.

A very effective way to denormalize a hierarchy is to create what are called "speed" tables. Figure 3 depicts a department hierarchy for a given organization. The hierarchic tree is built such that the top most node is the entire corporation and each of the other nodes represents a department at various levels within the corporation. In our example department 123456 is the entire corporation. Departments 1234 and 56 report directly to 123456. Departments 12, 3, and 4 report directly to 1234 and indirectly to department 123456. And so on.

The table shown under the tree in Figure 3 is the classic relational implementation of a hierarchy. There are two department columns, one for the parent and one for the child. This is an accurately normalized version of this hierarchy containing everything that is represented in the diagram. The complete hierarchy can be rebuilt with the proper data retrieval instructions.

Figure 3. Classic Relational Implementation of a Department Hierarchy

Even though the implementation effectively records the entire hierarchy, building a query to report all of the departments under any other given department can be time consuming to code and inefficient to process. Figure 4 shows a sample query that will return all of the departments that report to the corporate node 123456. However, this query can only be built if you know in advance the total number of possible levels the hierarchy can achieve. If there are n levels in the hierarchy then you will need n-1UNIONs.

Figure 4. Querying the Departmental Hierarchy

A "speed" table can be built such as the one in Figure 5. This table depicts the parent department and all of the departments under it regardless of the level. Contrast this to the previous table which only recorded immediate children for each parent. A "speed" table also commonly contains other pertinent information that is needed by the given application. Typical information includes the level within the hierarchy for the given node, whether or not the given node of the hierarchy is a detail node (at the bottom of the tree), and, if ordering within level is important, the sequence of the nodes at the given level.

Figure 5. Speed Table Implementation of a Departmental Hierarchy

After the "speed" table has been built, speedy queries can be written against this implementation of a hierarchy. Figure 6 shows various informative queries that would have been very inefficient to execute against the classical relational hierarchy. These queries work for any number of levels between the top and bottom of the hierarchy.

A "speed" table is commonly built using a program written in COBOL or another high level language. SQL alone is usually either too inefficient to handle the creation of a "speed" table or impractical because the number of levels in the hierarchy is either unknown or constantly changing.

Figure 6. Querying the Speed Table

Types of Denormalization

We have discussed nine different types of denormalization. The table below will summarize the types of denormalization that are available with a short description of when this type of denormalization is useful.

Summary

The decision to denormalize should never be made lightly because it involves a lot of administrative dedication. This dedication takes the form of documenting the denormalization decisions, ensuring valid data, scheduling of data migration, and keeping end users informed about the state of the tables. In addition, there is one more category of administrative overhead: periodic analysis.

Whenever denormalized data exists for an application the data and environment should be periodically reviewed on an on-going basis. Hardware, software, and application requirements will evolve and change. This may alter the need for denormalization. To verify whether or not denormalization is still a valid decision ask the following questions:

Have the processing requirements changed for the application such that the join criteria, timing of reports, and/or transaction throughput no longer require denormalized data?

Did a new DBMS release change performance considerations? For example, did the introduction of a new join method undo the need for pre-joined tables?

Did a new hardware release change performance considerations? For example, does the upgrade to a new high-end processor reduce the amount of CPU such that denormalization is no longer necessary? Or did the addition of memory enable faster data access enabling data to be physically normalized?

In general, periodically test whether the extra cost related to processing with normalized tables justifies the benefit of denormalization. You should measure the following criteria:

I/O saved
CPU saved
complexity of update programming
cost of returning to a normalized design

It is important to remember that denormalization was initially implemented for performance reasons. If the environment changes it is only reasonable to re-evaluate the denormalization decision. Also, it is possible that, given a changing hardware and software environment, denormalized tables may be causing performance degradation instead of performance gains.

Simply stated, always monitor and periodically re-evaluate all denormalized applications.

Craig S. Mullins is Vice President of Marketing and Operations for the database tools division of PLATINUM technology, inc. He has extensive experience in all facets of database systems development, including developing and teaching database and data modeling classes, systems analysis and design, database and system administration, and data analysis. Craig has worked with DB2 since V1 and has experience in multiple roles including programmer, DBA, instructor, and analyst. His experience spans industries having worked in manufacturing, banking, utilities, commercial software development, consulting and as a computer industry analyst for the Gartner Group. Additionally, Craig authored the popular DB2 Developer's Guide which provides over 1100 pages of tips, techniques, and guidelines to optimize DB2 for MVS.

Craig is also a frequent contributor to computer industry publications having over five dozen articles published during the past few years. His articles have been published in magazines like Byte, DB2 Update, Database Programming & Design, DBMS, Data Management Review, Relational Database Journal, Enterprise Systems Journal, Mainframe Client/Server and others.

Craig graduated cum laude with a degree in Computer Science and Economics from the University of Pittsburgh.

[The Article Archive]

The Data Administration Newsletter
Robert S. Seiner - Publisher and Editor - rseiner@tdan.com