Oliverro

Practical approach and requirements for a KdTree implementation

July 21st, 2011 | by | algorithms

Jul
21

I recently discovered and implemented in Java a kdtree with nearest neighbor search, query range search and point search functionality.
My KdTree implementation is non-dynamic (elements cannot be added after construction).

Description of what functionalities I needed for theses kdtree operations
KDTree construction :

Nearest Neighbors :

  • When comparing distance, use squared distance instead of the real distance.

Query range search :

  • Hyper rect intersection & containment method.
  • A rect associated with each Kdtreenode representing the area it can contains.
  • You start with an infinite rect and split it on each node cut.
  • From a point cut and an active axis, you must be able to compute the “right” and “left” part of the cutted rectangle.

Usage  :

KdTrees can be really efficient to reduce algorithms complexity.
For example, an naive implementation of a nearest segment search between 2 non-convex polygons would have a compexity of O(n^2) without a KdTree.
This complexity drops to O(n*log(n)) just by using a KdTree data structure for one of the polygon.

Remarks :
However we must always remember that building a KdTree uses some memory and is time consumming too.
KdTrees should only be used if the number of points is huge. For example, if you do want to use a KdTree to improve queries for 100 points you should better use a bruteforce naive algorithm which will reduce your developement time.

No Comments »

EJB injection with Spring-webmvc

April 27th, 2010 | by | java

Apr
27

Today I tried to integrate an EJB in a Spring MVC Controller. I’ll discuss my solution which is certainly not the best.
If you have a Spring MVC Controller which has a reference to an EJB it will not be resolved automatically by using the @EJB annotation.

As said in the spring documentation you can tell spring to inject the EJB for you.

Here is the configuration which worked for me :

In your servlet configuration file :

  1. Define a jee:local-slsb which points to your EJB
  2. Specify it as a property for your spring-bean (your controller).
  3. Don’t forget to add a setter for the your “service” in your controller.
<jee:local-slsb id="myService" jndi-name="java:comp/env/MyService"
business-interface="ch.myproject.services.MyServiceLocal" />
<bean name="myController"
class="ch.myproject.controllers.MyController">
<property name="service" ref="myService" />
</bean>

In your web.xml file

You also have to tell spring what is your “myService” by specifying an ejb-local-ref

<ejb-local-ref>
<ejb-ref-name>MyService</ejb-ref-name>
<local>ch.myproject.services.MyServiceLocal</local>
<ejb-link>MyService</ejb-link>
</ejb-local-ref>

No Comments »

JPA on GAE

April 26th, 2010 | by | java

Apr
26

Recently I had problems with JPA on Google App Engine when using @OneToMany relationships.
The data was well inserted in the database but the relationship was set to null after loading it.

Here is the entity :

@Entity
public class A implements Serializable
	{

	public A()
		{
		}

	public void setId(Long id)
		{
		this.id = id;
		}

	public void setName(String name)
		{
		this.name = name;
		}

	public List<B> getB()
		{
		return this.b;
		}

	public Long getId()
		{
		return this.id;
		}

	public String getName()
		{
		return this.name;
		}

	public List<B> getB()
		{
		return this.b;
		}
	@Id
	@GeneratedValue(strategy = GenerationType.IDENTITY)
	private Long id;

	private String name;

	@OneToMany(cascade = CascadeType.ALL)
	private List<B> b;

	}

Other posts (forums,blogs) talk about this problem. The workaround is to interact with the “List<B>” before closing the EntityManager. It can be done by calling a.b.size() before returning the entity.

No Comments »